백준 11780번 : 플로이드 2 in Python
이 문제는 이전에 해결했었던 플로이드 문제에 추가로 최소 비용을 가지는 경로를 출력해야 하는 문제이다.
그러므로 최소 비용을 출력하는 건 위 코드를 이용하면 된다. 문제는 최소 비용을 가지는 경로를 출력할 때, 지난 문제처럼 각 정점마다 최단 경로 위에서 해당 정점 이전에 지났던 정점을 저장하는 방식으로 경로를 저장하는 것이 불가능하다는 것이다. 왜냐하면 이 문제는 플로이드 와샬 알고리즘을 사용하는데, 이는 최단 경로의 정점을 순서대로 방문하는 방식이 아니기 때문이다. 그러므로 위 문제는 다른 방식으로 경로를 저장해야 한다.
여기서는 경로를 배열로 저장하는 방식을 사용한다. 예를 들어 만약 정점 1에서 정점 5로 가는 경로를 저장할 때 만약 정점 2, 4, 3을 지난다면 [1, 2, 4, 3, 5]로 경로를 저장하는 것이다. 그렇다면 플로이드 와샬 알고리즘을 진행 중일 때 어떻게 경로를 저장할 수 있을까?
우선 정점 i에서 출발해 정점 j에 도착하는 경로를 (i, j) 성분으로 가지는 행렬을 course라 정의하고, 이를 [i]로 초기화한다. 그 다음에 플로이드 와샬 알고리즘을 수행하는 도중에 만약 graph[i][j]가 graph[i][k] + graph[k][j]보다 크면 graph[i][j]를 수정하면서 course[i][j]를 course[i][k]에 해당하는 배열과 course[k][j]에 해당하는 배열을 합친다. 이를 k가 n이 될 때까지 진행하면 course[i][j]에는 정점 j를 제외한 최소 비용을 갖는 경로가 저장된다.
이후 최소 비용을 가지는 경로를 출력할 때 graph[i][j]가 0이거나 INF이면 경로가 없다는 뜻이므로 0을 출력하고, 그렇지 않은 경우 경로의 길이와 경로를 출력하면 된다.
이를 코드로 구현하면 다음과 같다.
import sys
n = int(input())
m = int(input())
graph = [[sys.maxsize]*(n+1) for _ in range(n+1)]
# 최소 비용을 가지는 경로를 저장하는 행렬
course = [[[i]]*(n+1) for i in range(n+1)]
for _ in range(m):
a, b, c = map(int, input().split())
graph[a][b] = min(graph[a][b], c)
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
if i == j:
graph[i][j] = 0
else:
if graph[i][j] > graph[i][k] + graph[k][j]:
graph[i][j] = graph[i][k] + graph[k][j]
# relax 과정에서 최소 비용을 가지는 경로를 수정한다.
course[i][j] = course[i][k] + course[k][j]
for i in range(1, n+1):
for j in range(1, n+1):
if graph[i][j] == sys.maxsize:
print(0, end=" ")
else:
print(graph[i][j], end=" ")
print()
for i in range(1, n+1):
for j in range(1, n+1):
# graph[i][j]가 sys.maxsize임은 i에서 j까지의 경로가 없음을 의미한다.
if graph[i][j] == 0 or graph[i][j] == sys.maxsize:
print(0)
else:
print(len(course[i][j])+1, " ".join(list(map(str, course[i][j]))), j)