1697번 - 숨바꼭질(Python)

풀이

dp 및 bfs를 이용해 목적지까지의 최단 시간을 계산한다.

X 위치까지의 최단 시간을 dp에 저장한다.

X 위치에서 이동할 수 있는 X-1, X+1, X*2 위치의 dp값을 dp[X]+1로 저장한다.

이들을 큐에 넣어 bfs를 실행한다.

방문 여부는 dp값을 -1과 비교하여 확인한다.

dp[K] 값을 구했다면, while문을 종료하고 답을 출력한다.

코드

from collections import deque

N, K = map(int, input().split())

dp = [-1 for _ in range(100001)]
dp[N] = 0
queue = deque([N])

while queue:
    node = queue.popleft()
    tmp = [node - 1, node + 1, node * 2]

    for t in tmp:
        if 0 <= t < 100001 and dp[t] == -1:
            dp[t] = dp[node] + 1
            queue.append(t)
    if K in tmp:
        print(dp[K])
        break