[백준] 1697 숨바꼭질 python

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

from collections import deque
n, k = map(int, input().split())
dp = [0] * 100001
q = deque([n])
dp[n] = 1
while q:
    x = q.popleft()
    if 0 <= x - 1 and dp[x - 1] == 0:
        dp[x - 1] = dp[x] + 1
        q.append(x - 1)
    if x + 1 <= 100000 and dp[x + 1] == 0:
        dp[x + 1] = dp[x] + 1
        q.append(x + 1)
    if x <= 50000 and dp[2 * x] == 0:
        dp[2 * x] = dp[x] + 1
        q.append(2 * x)
    #print(q)
    if dp[k]:
        break
#print(dp)
result = dp[k]-1
print(result)

dp를 사용해서 n에서 시작해서 k까지 갈때 모든 자리를 바꿔주었다.

bfs에서 최소거리를 구할때 사용한 방법을 사용해서 이전 자리보다 1씩 더 크게 만들었고

dp[k]가 0이 아닌지 계속 확인하면서 아닌경우 break을 걸어서 반복문을 빠져나왔다.