[백준알고리즘/13549번/파이썬] 숨바꼭질 3

https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

문제: 동생이 위치한 K에 도달할 수 있는 최단 기간을 출력하는 문제

 

풀이 방법: 다잌스트라

 

풀이 코드:

import sys
import heapq

MAX = 100001
n,k = map(int,sys.stdin.readline().rstrip().split())


distance = [1e9] * MAX
visited = [False] * MAX
distance[n] = 0

q = [[0,n]]

def dijkstra():
    while q:
        nowCost, nowNode = heapq.heappop(q)
        visited[nowNode] = True

        if nowNode == k:
            break

        move = [[nowCost, nowNode*2], [nowCost + 1, nowNode - 1], [nowCost+1, nowNode+1]]

        for i in range(3):

            if move[i][1] >= MAX or move[i][1] < 0 or visited[move[i][1]]:
                continue

            if distance[move[i][1]] > move[i][0]:
                distance[move[i][1]] = move[i][0]
                heapq.heappush(q,move[i])


dijkstra()
print(distance[k])