[백준] 13549번 숨바꼭질3 (파이썬)

난이도 : GOLD III

문제링크 : https://www.acmicpc.net/problem/13549

문제해결 아이디어

• +1 -1 씩 이동할때는 가중치가 1씩 증가하고 x2씩 증가할때는 가중치가 0이므로 다익스트라 알고리즘으로 풀어야겠다고 생각했다.

소스코드

import sys
import heapq

input = sys.stdin.readline

n,m = map(int,input().split())
INF = int(1e9)
_max = 100001
distance = [INF] * _max
distance[n] = 0        
def dijk(start,m):        
    h = []
    heapq.heappush(h, (0,start))
    while h:
        dist,now = heapq.heappop(h)

        if distance[now] < dist:
            continue

        for nx in [now+1, now-1, 2*now]:
            if 0<=nx<_max:
                if nx == 2*now :
                    if dist < distance[nx]:
                        heapq.heappush(h, (dist, nx))
                        distance[nx] = dist
                else :
                    if dist + 1 < distance[nx]:
                        heapq.heappush(h, (dist+1, nx))
                        distance[nx] = dist+1
    print(distance[m])
dijk(n,m)