[BaekJoon] 백준 11779번 : 최소비용 구하기 2

11779번 : 최소비용 구하기 2

다익스트라를 통해 출발점과 도착점 사이의 최단 거리를 구하면 되는 문제이다.

다만 여기서 최단 경로도 함께 구하면 된다.

스페셜 저지이기 때문에 최단 경로가 여러 개가 있더라도 한 가지 경우만 출력하면 된다.

최단 경로를 구하는 방법은 거리가 갱신될 때마다 경로도 같이 갱신해 주는 방법을 사용했다.

하지만 거리가 매 번 갱신 된다면 시간이 많이 걸린다.

지금까지 거쳐온 모든 경로를 저장하지 않고 바로 이전에 방문했던 노드만 저장하는 방법으로도 경로를 구할 수 있다.

---

[경로도 같이 갱신하는 방법]

import sys
import heapq
from copy import deepcopy


def solution():
    distance = [[float('inf'), [start]] for _ in range(N + 1)]
    distance[start][0] = 0

    queue = []
    heapq.heappush(queue, (0, start))

    while queue:
        dist, now = heapq.heappop(queue)
        if distance[now][0] < dist:
            continue

        for edge in graph[now]:
            visit, cost = edge
            if dist + cost < distance[visit][0]:
                path = deepcopy(distance[now][1])
                path.append(visit)
                distance[visit][1] = path
                distance[visit][0] = dist + cost
                heapq.heappush(queue, (dist + cost, visit))

    print(distance[end][0])
    print(len(distance[end][1]))
    print(*distance[end][1])


if __name__ == "__main__":
    N = int(input())
    M = int(input())
    graph = {i + 1: [] for i in range(N)}

    for _ in range(M):
        start, end, cost = map(int, sys.stdin.readline().rsplit())
        graph[start].append((end, cost))

    start, end = map(int, sys.stdin.readline().rsplit())

    solution()

---

[이전에 방문했던 노드만 저장하는 방법]

import sys
import heapq
from collections import deque


def solution():
    path = [0] * (N + 1)
    distance = [float('inf')] * (N + 1)
    distance[start] = 0

    queue = []
    heapq.heappush(queue, (0, start))

    while queue:
        dist, now = heapq.heappop(queue)
        if distance[now] < dist:
            continue

        for edge in graph[now]:
            visit, cost = edge
            if dist + cost < distance[visit]:
                path[visit] = now
                distance[visit] = dist + cost
                heapq.heappush(queue, (dist + cost, visit))

    result = deque([])
    i, j = start, end
    while path[j] != i:
        result.append(path[j])
        j = path[j]
    result.reverse()
    result.appendleft(start)
    result.append(end)

    print(distance[end])
    print(len(result))
    print(*result)


if __name__ == "__main__":
    N = int(input())
    M = int(input())
    graph = {i + 1: [] for i in range(N)}

    for _ in range(M):
        start, end, cost = map(int, sys.stdin.readline().rsplit())
        graph[start].append((end, cost))

    start, end = map(int, sys.stdin.readline().rsplit())

    solution()