문제링크

설명

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

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

아이디어

모든 경로를 탐색하는 것(DFS)이 아닌 가장 빠른 시간(최단시간) → BFS

2배로 이동하는 경우(순간이동), 걷는 경우(한칸 뒤로, 한칸 앞으로)를 큐에 저장해서 동생의 위치(K)까지 도착하는 최단시간을 구함

예시

5 → 라는 입력이 있었을 경우 17 → Target

queue = [(5,0)] → [(4,1),(10,0),(6,1)] → [(3,2),(8,1),(6,2),(9,1),(20,0),(11,1), ...]

→ [(2,3),(6,2),(4,3) … (18,1) ...]

→ [… , 17,2 , …] (절대 쓰다가 귀찮아서 생략한 거 아니에요)

from collections import deque

def bfs(x, cnt):
    queue = deque()
    queue.append((x, cnt))

    while queue:
        x, cnt = queue.popleft()
        visited[x] = 1

        if (x == k):
            return cnt

        for nx in [2 * x, x - 1, x + 1]:
            if 0 <= nx <= 100000:
                if visited[nx] == 0:
                    if nx == 2 * x:
                        queue.append((nx, cnt))
                    else:
                        queue.append((nx, cnt + 1))

n, k = map(int, input().split())
visited = [0] * 100001
print(bfs(n, 0))