[BOJ13549 숨바꼭질3] BFS (Python)

문제조건

• 걷기 (x+1 또는 x-1 이동)는 1초가 걸리고,
• 순간이동(2*x 이동)은 0초가 걸린다.

핵심개념

• 그래프 문제로 안 보이지만, 그래프로 변형해서 푼다.
• BFS로 최단거리를 구하려면 가중치가 1이어야 한다. 그런데 가중치가 1이 아닌 경우(0초 같은), deque를 사용한다.

코드

from collections import deque
MAX = 200000 
check = [False]*MAX
dist = [-1]*MAX
n,m = map(int,input().split())

check[n] = True
dist[n] = 0
q = deque()
q.append(n)

while q:
    now = q.popleft()
    if now*2 < MAX and check[now*2] == False:
        q.appendleft(now*2)
        check[now*2] = True
        dist[now*2] = dist[now]
    if now-1 >= 0 and check[now-1] == False:
        q.append(now-1)
        check[now-1] = True
        dist[now-1] = dist[now]+1
    if now+1 < MAX and check[now+1] == False:
        q.append(now+1)
        check[now+1] = True
        dist[now+1] = dist[now]+1

print(dist[m])