[Baekjoon 11779] 최소비용 구하기

문제

💛Ⅲ [Baekjoon 11779 - 최소 비용 구하기]

문제 풀이 방법

최단경로를 구하는 것이므로 다익스트라 알고리즘 문제이다. 하지만 경로까지 구해야 하기 때문에 문제를 푸는데 꽤 많은 시간이 걸렸다. 처음에는 경로를 축적하여 구하기 위해서 매개변수에 path 배열을 추가하여 최단 거리를 갱신할 때마다 path에 노드를 추가해주었다. 하지만 이 경우 중복 값이 많이 나오고, 메모리 복잡도가 좋지 않았다… 질문하기 게시판을 참고한 결과 노드의 전 노드의 값을 저장해주면 배열 하나로 경로가 추적가능했다. (왜 이런 생각을 못했을까..?)

1. 다익스트라 알고리즘을 수행한다.
   1. 최단경로를 갱신하는 경우 parent 배열에서 현재 노드 인덱스에 현재 노드에 도달하기 위한 전 노드를 대입해준다.
2. 최단거리를 출력한다.
3. 경로를 출력한다.
   1. 마지막 노드를 시작으로 처음 노드의 값이 나올 때까지 parent 배열에서 경로를 거꾸로 추적한다.
   2. 경로를 거꾸로 출력한다.

풀이 코드

Python

import sys, heapq
input = sys.stdin.readline

INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF]*(n+1) for _ in range(n+1)]
parent = [-1] * (n+1)
distance =  [INF] * (n +1)

for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a][b] = min(c, graph[a][b])

start_node, end_node = map(int, input().split())

def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 0
    while q:
        dist, node = heapq.heappop(q)
        if distance[node] < dist:
            continue
        for next_node,d in enumerate(graph[node]):
            if next_node == 0: continue
            cost = d + dist
            if cost < distance[next_node]:
                distance[next_node] = cost
                parent[next_node] = node
                heapq.heappush(q,(cost, next_node))

dijkstra(start_node)
print(distance[end_node])
paths = [end_node]
while paths[-1] != start_node:
    paths.append(parent[paths[-1]])
print(len(paths))
for p in paths[::-1]:
    print(p, end=" ")