백준 11779번 : 최소비용 구하기 2 in Python

11779번: 최소비용 구하기 2

 

www.acmicpc.net

이 문제는 한 도시에서 다른 도시로 가는데 드는 버스 비용을 최소화하는 최소비용과 경로를 출력하는 문제이다.

이는 이전에 다루었던 dijkstra algorithm을 적용하면 풀 수 있는 문제이나, 이전의 문제들과는 달리 이러한 최소비용이 나오게 된 경로까지 출력해야 한다. 그래서 이전에 구현했던 최단 경로 문제에 경로를 저장하는 records 배열을 새로 추가한다.

백준 1753번 : 최단경로 in Python

1753번: 최단경로 www.acmicpc.net 이 문제는 각 간선마다 가중치가 있을 경우 시작점으로부터 다른 모든 정점으로의 최단 경로를 구하는 문제이다. 기존의 최단경로 문제의 경우 모든 간선의 가중치가 같았지만,..

wanna-be-developer-yjh.tistory.com

그리고 (u, v) 간선을 relax하는 과정에서 records[v]를 u로 저장한다. 즉, 시작 도시에서 v라는 도시에 도달하기 위해 최단 경로로 이동할 때 도시 u를 선행자로 거쳐야 함을 의미한다. 그러면 dijkstra 알고리즘을 끝냈을 때 records 배열을 통해 시작 도시에서 목표 도시까지 최단 경로로 이동하기 위해 어떤 도시를 거쳐야 하는지를 추적할 수 있다.

우선 path라는 배열을 만들고, 여기에는 목표 도시를 넣는다. 그리고 k가 시작 도시가 아닌 동안 path 배열에 records[k]를 넣고 k의 값을 records[k]로 바꾸는 과정을 반복한다. 그러면 path에는 시작 도시에서 목표 도시로 가기 위한 경로가 역으로 저장된다. 따라서 출력할 때는 이를 뒤집어주면 된다.

이를 코드로 구현하면 다음과 같다.

import heapq
import sys
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append([b, c])
start, end = map(int, input().split())
dijk = [sys.maxsize for _ in range(n+1)]
visited = [False for _ in range(n+1)]
# 최단 경로를 기록하기 위한 배열
records = [i for i in range(n+1)]
dijk[start] = 0
heap = []
heapq.heappush(heap, [0, start])
# dijkstra 알고리즘
while len(heap) > 0:
    [d, u] = heapq.heappop(heap)
    visited[u] = True
    for [v, c] in graph[u]:
        if not visited[v] and dijk[v] > dijk[u] + c:
            dijk[v] = dijk[u] + c
            # 최단 경로를 저장하는 코드를 dijkstra algorithm에 추가한다.
            records[v] = u
            heapq.heappush(heap, [dijk[v], v])
print(dijk[end])
# 최단 경로를 출력하기 위한 코드
k = end
path = [str(k)]
while k != start:
    path.append(str(records[k]))
    k = records[k]
path.reverse()
print(len(path))
print(" ".join(path))