[백준(파이썬/Python)] 11779_최단경로 구하기2 - 다익스트라

https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

이 문제는 다익스트라 알고리즘을 통해 최단거리를 구한 후, 최단 거리에 대한 경로를 출력을 요구하고 있습니다.

 

따라서, 일반적인 다익스트라 구현에 경로를 출력하기 위한 구현이 추가로 필요한데 이 부분은 아래 코드에서 parents라는 딕셔너리로 구현햇습니다. 현재 지점에서 다른 지점으로 넘어가면서 최단거리를 갱신할 때 다음 지점의 부모를 현재 지점으로 설정해주는 것이죠.

 

그러면 마지막에 결과값을 출력할때는 맨 마지막 노드부터 거꾸로 부모를 출력해주면 되겠죠.

 

예를 들어 문제에서 주어진 테스트 케이스는 아래와 같습니다.

여기서 다익스트라 알고리즘을 수행하게 되면 아래와 같은 트리 형태로 최단 거리가 갱신된다.

그러면 맨 처음 순회에서 2, 3, 4, 5번 노드의 부모는 1번 노드로 설정이 되고, 이 때 parents = {2:'1', 3:'1', 4:'1', 5:'1'}이 됩니다.

다음으로, 4번 노드에서 5번 노드로 갈 때 최단거리가 갱신되면 5번 노드의 부모가 4번 노드가 되기 때문에 parents = parents = {2:'1', 3:'1', 4:'1', 5:'4'}가 됩니다.

 

따라서, 경로를 출력해줄 때는 도착지점(5번 노드) -> 5번 노드의 부모(4번 노드) -> 4번 노드의 부모(1번 노드)를 역으로 출력해주면 됩니다.

 

이를 구현한 풀이는 아래와 같습니다.

 

[풀이]

import sys,heapq
from collections import defaultdict

def dijkstra(start):
    # 경로를 구하기 위한 부모 초기화
    for c in range(1, n+1):
        if c != start:
            parents[c] = None

    pq = []
    heapq.heappush(pq,(0, start))
    while pq:
        curr_cost, curr = heapq.heappop(pq)
        if distance[curr] < curr_cost:
            continue
        
        for next in graph[curr]:
            next_cost, next_node = next[0], next[1]
            
            if curr_cost + next_cost < distance[next_node]:
                heapq.heappush(pq, (curr_cost + next_cost, next_node))
                distance[next_node] = curr_cost + next_cost
                
                # 현재 노드를 다음 노드의 부모로 지정한다.
                parents[next_node] = curr                

    # 시작부터 끝점까지 경로 생성하기
    route = []
    current = end
    while current != start:
        route.append(current)
        current = parents[current]
    route.append(start)
    route.reverse()
    return route



    return route
input = sys.stdin.readline
inf = int(1e9)

n, m = int(input()), int(input())
# 간선 정보 입력하기
graph = [[] for _ in range(n+1)]
for _ in range(m):
    s, e, cost = map(int, input().split())
    graph[s].append((cost, e))

# 시작점, 도착점 정보 입력받기
start, end = map(int, input().split())

# 출발 도시부터 다른 도시까지 최단 거리를 저장하는 리스트
distance = [inf] * (n+1)
distance[start] = 0

# 경로 추적을 위한 딕셔너리
parents = defaultdict()

route = dijkstra(start)
print(distance[end])
print(len(route))
print(*route)