백준 1719 : 택배 (Python)

본문 링크

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

def Dijkstra(start):

    dp=[INF]*(N+1) ; dp[start]=0
    Route=[0]*(N+1) ; heap=[] ; heapq.heappush(heap , (0,start))

    while heap:

        value,node=heapq.heappop(heap)

        if dp[node]<value:
            continue

        for next_value,next_node in graph[node]:

            next_value+=value

            if next_value<dp[next_node]:
                dp[next_node]=next_value
                Route[next_node]=node
                heapq.heappush(heap , (next_value , next_node))

    return Route

N,M=map(int,input().split())
graph=[ [] for _ in range(N+1) ]


for i in range(M):
    A,B,C=map(int,input().split())
    graph[A].append((C,B))
    graph[B].append((C,A))


for i in range(1,N+1):
    Answer=Dijkstra(i)
    for j in range(1,N+1):
        P = []
        tmp=j
        while tmp!=0:
            P.append(tmp)
            tmp=Answer[tmp]


        if i!=j:
            print(P[-2] , end=" ")
        else:
            print("-" , end=" ")
    print()

📌 어떻게 접근할 것인가?

다익스트라를 통해 풀었습니다.

문제에서 원하는 것은 특정 노드에서 다른 노드로 이동할때 최단경로로 이동했을때
가장 먼저 방문하는 노드를 찾는 것입니다.

역추적을 하기 위해서 Route 라는 배열을 만들어 주고 Route[next_node]=node 다음 이동할 노드에 이전의 노드 번호를 저장합니다.

이후 다익스트라를 끝내면 이 배열을 반환합니다.

tmp=j
while tmp!=0:
	P.append(tmp)
	tmp=Answer[tmp]

이후 역추적을 해줍니다. 매번 tmp 값을 P 배열에 저장했습니다.

i==j 인경우는 - 를 출력하고 그렇지 않을 경우 P[-2] 를 출력합니다.
인덱스를 음수로 쓴 이유는 역추적은 뒤에서부터 출발하지만 문제에서 원하는 것은 처음부터 시작해서 처음으로 방문하는 지점이기 때문에 시렞로 P 배열에는 도착지점에서 시작지점으로 가는 경로가 담겨있습니다.

또한 -1 이 아니라 -2 를 넣은 이유는 도착지점에서 시작지점으로 갈때 가장 마지막에 방문한 지점은 원래의 시작지점이기 때문입니다.