[백준 13549] 숨바꼭질 3 (python) 우선순위 큐를 이용한 구현

 

 

 

 

순간이동의 경우 시간 소모가 0초이다.

따라서 스택과 큐를 이용하여 그래프를 순회하게 될 경우에는 최단거리를 찾을 수 없게 된다.

그래서 떠올린 것이 우선순위 큐이다. 

 

우선순위 큐를 이용하여 순간이동을 우선적으로 탐색하여 최단거리를 찾을 수 있었다. 

from queue import PriorityQueue
N, K = map(int, input().split(" ")) 

def BFS(start, end):
  queue = PriorityQueue()
  queue.put((0, start))
  visited = [int(0) for _ in range(100001)]
  while queue:
    cost,now = queue.get()
    if now == end:
      return cost
    visited[now] = 1
    if now * 2 <= 100000 and visited[now*2] == 0:
      queue.put(( cost, now*2 ))
    if now -1 >= 0 and visited[now-1] == 0:
      queue.put((cost +1,now-1 ))
    if now +1 <= 100000 and visited[now+1] == 0:
      queue.put((cost +1,now+1 ))

print(BFS(N,K))