시간 제한	메모리 제한
2 초	512 MB

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

풀이

이 문제는 가중치가 다른 간선이 있는 그래프에서의 최단 경로 문제이다.

X → X+1, X → X-1: 비용 1
X → 2*X: 비용 0

접근 방법

다익스트라 알고리즘 사용

가중치가 다른 간선이 있으므로 다익스트라 알고리즘을 사용한다. 일반 BFS는 모든 간선의 가중치가 1일 때만 최단 경로를 보장한다.

핵심 아이디어

현재 위치에서 갈 수 있는 세 가지 선택지:
- X+1 (비용 1)
- X-1 (비용 1)
- 2*X (비용 0)
우선순위 큐를 사용하여 비용이 작은 경로부터 탐색
각 위치까지의 최소 비용을 갱신하며 탐색

코드

import heapq
INF = float('inf')

N, K = map(int, input().split())
distance = [INF] * 100001

def dijkstra(start):
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        dist, c = heapq.heappop(q)
        if distance[c] < dist:
            continue
        for n in (c+1, c-1, c*2):
            if n < 0 or n > 100000:
                continue

            cost = dist
            if n != c*2:
                cost = dist + 1

            if cost < distance[n]:
                distance[n] = cost
                q.append((cost, n))

dijkstra(N)
print(distance[K])

코드 설명

초기화

INF = float('inf')
distance = [INF] * 100001

각 위치까지의 최소 비용을 저장할 배열
초기값은 무한대(INF)

다익스트라 함수

def dijkstra(start):
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))

시작 위치의 비용은 0
우선순위 큐에 (비용, 위치) 튜플 저장

탐색 과정

while q:
    dist, c = heapq.heappop(q)
    if distance[c] < dist:
        continue

우선순위 큐에서 비용이 가장 작은 위치를 꺼냄
이미 처리된 경우(더 짧은 경로로 방문됨) 건너뜀

이동 처리

for n in (c+1, c-1, c*2):
    if n < 0 or n > 100000:
        continue

    cost = dist
    if n != c*2:
        cost = dist + 1

    if cost < distance[n]:
        distance[n] = cost
        q.append((cost, n))

세 가지 이동 방법 확인
범위 체크 (0 ≤ n ≤ 100,000)
순간이동(2*X)은 비용 0, 걷기는 비용 1
더 짧은 경로를 발견하면 갱신하고 큐에 추가

시간 복잡도

다익스트라 알고리즘: O((V + E) log V)
V = 100,001 (위치의 개수)
각 위치에서 최대 3개의 간선: E ≤ 3V
전체: O(V log V) ≈ O(100,000 × 17) = O(1,700,000)

시간 제한 2초 내에 충분히 해결 가능하다.

0-1 BFS를 이용한 최적화

비용이 0 또는 1만 있는 경우 deque를 사용한 0-1 BFS로 더 효율적으로 해결할 수 있다:

from collections import deque

N, K = map(int, input().split())
distance = [float('inf')] * 100001

def bfs_01(start):
    dq = deque([(0, start)])
    distance[start] = 0
    
    while dq:
        dist, c = dq.popleft()
        
        if distance[c] < dist:
            continue
            
        # 비용 0인 간선 (순간이동)
        n = c * 2
        if 0 <= n <= 100000 and dist < distance[n]:
            distance[n] = dist
            dq.appendleft((dist, n))  # 앞에 추가
        
        # 비용 1인 간선 (걷기)
        for n in (c + 1, c - 1):
            if 0 <= n <= 100000 and dist + 1 < distance[n]:
                distance[n] = dist + 1
                dq.append((dist + 1, n))  # 뒤에 추가

bfs_01(N)
print(distance[K])

0-1 BFS의 핵심:

비용 0인 간선: appendleft() (앞에 추가)
비용 1인 간선: append() (뒤에 추가)
이렇게 하면 큐가 항상 비용 순으로 정렬됨

주의 사항

범위 체크: 0 ≤ 위치 ≤ 100,000
순간이동 우선: 순간이동(비용 0)을 먼저 처리하면 더 효율적
중복 방문 처리: 이미 더 짧은 경로로 방문한 경우 건너뛰기
우선순위 큐: 일반 큐가 아닌 우선순위 큐 사용 필수

[BOJ] 숨바꼭질 3 - 13549 (G5)

문제

입력

출력

풀이