백준 1697 : 숨바꼭질 (bfs, Python)

문제

1697번: 숨바꼭질

 

입력 : n=수빈시작위치, k=동생위치(도착지점)

출력 : 수빈이가 걷거나 순간이동한 횟수 

 

예를들어 n=5, k=17 일떼, 수빈이가 5-10-9-18-17 순으로 가면 4번 만에 동생을 찾을 수 있다.

 

 

풀이

from collections import deque

MAX=10**5
dp=[0]*(MAX+1)
dq = deque()

n,k = map(int,input().split())
dq.append(n)
while dq:
    c=dq.popleft() #current
    if c==k:
        print(dp[k])
        break

    for nc in (c-1,c+1,c*2):
        if 0<=nc<=MAX and dp[nc]==0:
            dp[nc]=dp[c]+1
            dq.append(nc)

 

큐에 현재 위치 c와 다음 위치 c-1, c+1, c*2를 넣으며 횟수를 추가했다.