백준 13913 : 숨바꼭질 4 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline
INF=int(1e9)

def Dijkstra(start):

    global visit

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

    while heap:

        value,node=heapq.heappop(heap)

        if dp[node]<value:
            continue

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

            if 0<=next_node<=100000 and next_value<dp[next_node]:
                dp[next_node]=next_value

                visit[next_node]=node #  역추적 하기 위해서 이동할 지점에 현재노드값 저장.

                heapq.heappush(heap, (next_value , next_node))

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

dp=[INF]*(100001)
visit=[0]*(100001)
Dijkstra(N)
Answer=[] ; tmp=K

while tmp!=N:
    Answer.append(tmp)
    tmp=visit[tmp] #역추적

Answer.append(N)
print(dp[K])
print(*Answer[::-1])

📌 어떻게 접근할 것인가?

기존의 숨바꼭질 3 문제를 살짝변형시켰습니다.
$-1$ , $1$ , $2$배 이동 가능하며 이동할때 드는 가중치는 $+1$ 입니다.

다익스트라로 구현했고 경로를 역추적 하기 위해서 visit 배열을 선언했습니다.
이때 이동가능한 경로가 존재하면 visit 배열에 이동할 지점에 현재 노드값을 저장합니다.

이후 최단경로를 찾은 후에 도착지점부터 역추적해서 이전에 이동했던 지점은 tmp 가 end 로 초기값을 설정하고 visit[tmp] 가 이전에 이동했던 지점이 되고

계속 이전의 이동했던 지점으로 이동해서 시작점이 될때까지 계속 반복합니다.

이후 역추적을 저장한 배열을 역순으로 출력하면 이동경로를 구할 수 있습니다.

아주 중요한 테크닉이니 꼭 기억해야합니다.