문제 n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.
입력 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.
출력 첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.
둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.
셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다.
이 문제는 일반적인 다익스트라 문제에서, 경로들을 모두 역추적을 해야 하는 문제다.
즉, 기존의 다익스트라 문제가 최소 비용만을 구하는 문제였다면, 이 문제는 그 최소비용이 된 경로들을 모두 순서대로 출력을 해야 하는 문제다.
이럴 경우, 기존의 다익스트라 알고리즘을 사용하되, 그 경로까지 Save를 해야 하는 추가적인 과정을 거친다.
따라서, 최소비용을 구하는 과정에서 각 노드 별로 자신의 이전 노드를 저장하는 추가 절차를 구현 했다.
이 문제가 조금 까다로웠던 이유는, 자신의 이전 노드를 저장하는 것을 너머, 그 경로를 역추적 해야 하는 점이 문제였다.
따라서 다음과 같이 각 노드 별로 자신의 이전 노드를 저장하는 배열을 추가로 선언했다.
pred = [0 for _ in range(n+1)]이 pred테이블은 이 곳에서 값이 갱신된다.
while heap:
now_node, wei = heapq.heappop(heap)
if wei > table[now_node]:
continue
for new_node, w in graph[now_node]:
sum = w + wei
if table[new_node] > sum:
table[new_node] = sum
pred[new_node] = now_node
heapq.heappush(heap, (new_node, sum))Greedy한 접근법으로 간선을 선택하여 다음 노드로 넘어갈 때, 우리는 새로운 목적지 new_node를 알고 있다.
이를 이용해서, new_node로 넘어가기 전, pred[new_node] = now_node를 통해 다음 목적지의 노드에 이전 노드의 정보를 저장한다.
이 과정은 전체 간선을 순회하며 계속해서 값이 갱신되기 때문에 while loop이 종료되면, 자신의 이전 노드에 대한 값이 저장된다.
그 후, 경로를 역으로 추적하여 갱신하기 위해 다음과 같은 재귀함수를 선언했다.
def find_prev(forw_node):
global ans
ans.append(forw_node)
if forw_node == ts:
print(table[tf])
print(len(ans))
ans.reverse()
print(*ans)
exit()
prev_node = pred[forw_node]
find_prev(prev_node)forw_node가 처음 노드가 될 때 까지, 역으로 추적해서 경로를 그려 나간다. 최종적으로 ans 배열에는 경로의 순서까지 고려하여 경로가 생성된다.
이 문제를 풀 때 역으로 추적하는 과정에서 굉장히 애를 먹었다. 재귀 함수를 호출하는 과정에서 무한 재귀에 빠지거나, prev 함수가 제대로 갱신이 되지 않아 시간 초과가 많이 발생했다.
import heapq
import sys
n = int(input())
m = int(input())
INF = sys.maxsize
graph = [[] for _ in range(n+1)]
table = [INF for _ in range(n+1)]
pred = [0 for _ in range(n+1)]
ans = []
heap = []
for _ in range(m):
s,f,c = map(int,input().split())
graph[s].append((f,c))
ts, tf = map(int,input().split())
heapq.heappush(heap, (ts,0))
table[ts] = 0
pred[ts] = ts
while heap:
now_node, wei = heapq.heappop(heap)
if wei > table[now_node]:
continue
for new_node, w in graph[now_node]:
sum = w + wei
if table[new_node] > sum:
table[new_node] = sum
pred[new_node] = now_node
heapq.heappush(heap, (new_node, sum))
def find_prev(forw_node):
global ans
ans.append(forw_node)
if forw_node == ts:
print(table[tf])
print(len(ans))
ans.reverse()
print(*ans)
exit()
prev_node = pred[forw_node]
find_prev(prev_node)
find_prev(tf)