[다익스트라] (백준) 숨바꼭질 3 - 파이썬

✅ 이동시 -1 이 있으므로 최대 max(N,K)*2만큼의 배열이 필요하다 (입력이 5 17 일때 : 5->10->20->17)

import heapq
INF = int(1e9)
N,K = map(int,input().split())
distance = [INF]*(max(N,K)*2+1)

def dijkstra(start):
    distance[start]=0
    q=[]
    heapq.heappush(q,(0,start))
    while q:
        dist, now = heapq.heappop(q)
        if distance[now]<dist:
            continue
        for dd,dn in [(1,-1),(1,1),(0,now)]:
            next_dist = dist+dd
            next_now = now+dn
            if not ( 0<=next_now <=max(N,K)) :
                continue
            if distance[next_now]>next_dist:
                distance[next_now]=next_dist
                heapq.heappush(q,(next_dist,next_now))

dijkstra(N)
print(distance[K])