[백준] 13549번-(Python 파이썬) - Dijkstra

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

이번 문제는 다양한 숨바꼭질 문제와는 다르게 가중치가 다르게 되어있는 문제이다.
순간이동은 0초, 걸어서는 1초가 걸리는게 핵심이다.

가중치가 모두 같은 1 이었을때는 평범하게 bfs나 dfs알고리즘으로 쉽게 찾아가면 되지만
이번엔 가중치가 다르기에 다익스트라 알고리즘을 이용하여 풀었다.

현재 수빈이가 동생보다 앞에 있는경우엔 그냥 뺀 값을 출력을 하고,
순간이동을 하는 경우엔 가중치를 그냥 넘겨주고 걸어갈 경우엔 + 1초를 하는 방식으로 구현하였다.

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
inf = sys.maxsize

n, k = map(int, input().split())
dp = [inf] * (100001)
heap = []

def dijkstra(n, k):
    if k <= n:
        print(n - k)
        return
    
    heappush(heap, [0, n])
    while heap:
        w, n = heappop(heap)
        for nx in [n + 1, n - 1, n * 2]:
            if 0 <= nx <= 100000:
                if nx == n * 2 and dp[nx] == inf:
                    dp[nx] = w
                    heappush(heap, [w, nx])
                elif dp[nx] == inf:
                    dp[nx] = w + 1
                    heappush(heap, [w + 1, nx])
    print(dp[k])

dijkstra(n, k)