백준 13549 : 숨바꼭질 3 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline

def Dijkstra(N):

    dp[N]=0
    heap=[]
    heapq.heappush(heap,(0,N))

    while heap:

        value,node=heapq.heappop(heap)

        if dp[node]<value:
            continue

        for value,node in [(value+1,node+1) , (value+1,node-1),(value,node*2)]:

            if 0<=node<=100000 and value<dp[node]:
                dp[node]=value
                heapq.heappush(heap,(value,node))

N,K=map(int,input().split())

INF=int(1e9)
dp = [INF] * (100001)

Dijkstra(N)

print(dp[K])

📌 어떻게 접근할 것인가?

$BFS$ 로도 풀수 있지만 다익스트라를 이용해 풀었습니다.
heapq 라이브러리를 불러와주고 dp 배열을 INF 로 초기화 해주었습니다.
그리고 이동가능한 정점중에 가중치가 더 적은 지점이 있다면 그 노드로 이동해줍니다.
이후 문제에서 원하는 K 번째 노드의 값 , 즉 이동횟수를 출력해줍니다.