BaekJoon 13549번 : 숨바꼭질 3 (python)

BaekJoon 13549번 : 숨바꼭질 3 (G5 24.151%)

저번에 DFS/BFS 단계별 문제에서 풀어보았던 BFS 문제이다.

• 이번 조건에서는 순간이동을 하는 경우만 가중치가 0으로 따져야 하는 문제이다.
• start부터 -1,1,2배를 탐색하며 조건에 부합할 경우 distance 최단 경로를 업데이트 하는데
  -1과 1의 경우는 가중치를 +1 업데이트 해주고 2배일 경우는 value를 그대로 업데이트 하게 된다.

import sys, heapq
input = sys.stdin.readline
INF = 1e10

def dijkstra(start) :
    q = list()
    heapq.heappush(q,(start,0))
    distance[start] = 0
    while q :
        now, value = heapq.heappop(q)
        if distance[now] < value :
            continue
        for i in [-1,1,now] :
            next = now + i
            if 0<= next <= 100000 and distance[next] > value :
                if i == now :
                    distance[next] = value
                    heapq.heappush(q,(next,distance[next]))
                else :
                    distance[next] = value + 1
                    heapq.heappush(q,(next,distance[next]))

N, K = map(int,input().split())
distance = [INF]*100001
dijkstra(N)
print(distance[K])