[백준] 11780 - 플로이드 2 (Python)

 

https://www.acmicpc.net/problem/11780

 

학교 알고리즘 분석 전공 수업시간에 배웠던 내용을 그대로 이용하면 쉽게 풀 수 있는 문제이다.

플로이드 알고리즘은 dp 를 이용하는 방법으로, node 개수가 많지 않을 때 사용할 수 있는 알고리즘이다.

시간복잡도는 node 개수가 n개 일 때, O(n³) 의 시간복잡도를 갖는다.

 

두 노드 a, b 사이의 최단거리 a, b 를 dist[a][b] 라고 할 때, 

 

dist[a][b] = min( for k in range 1 .. n, dist[a][k] + dist[k][b] )

 

로 정의할 수 있다.

 

글로 정리하면, 두 노드 사이의 최단 거리는 그 노드 사이를 k 번 노드를 경유해서 갈 때 더 짧다면 그 값으로 갱신하는 과정을 거치면 된다.

 

이제 이를 역추적해보자.

 

우선 두 노드 a, b 사이를 k 번째 노드가 지나야 한다고 할 때, 이 정보를 parent[a][b] = k 로 저장하면 된다.

그리고 이를 역추적할 때는 a, b 노드 사이를 가는 최단 경로는 a, k, b 로 보면 된다.

그리고 이 경로에 대해 다시 (a, k) 사이의 경로를 구하고, (k, b) 사이의 경로르 구하는 과정을 재귀적으로 반복하면 된다.

 

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
INF = 98765432120
dist = [[INF for _ in range(n+1)] for _ in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
for _ in range(m):
    a, b, c = map(int, input().split())
    dist[a][b] = min(dist[a][b], c)

parent = [[0 for _ in range(n+1)] for _ in range(n+1)]

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                parent[i][j] = k

for i in range(1, n+1):
    for j in range(1, n+1):
        if dist[i][j] == INF:
            dist[i][j] = 0

for i in range(1, n+1):
    print(*dist[i][1:])


def get_path(_i, _j):
    if parent[_i][_j] == 0:
        return (_i, _j)
    interval = parent[_i][_j]
    path_front = get_path(_i, interval)
    path_back = get_path(interval, _j)
    return path_front + path_back[1:]


for i in range(1, n+1):
    for j in range(1, n+1):
        if dist[i][j] == 0:
            print(0)
        else:
            if parent[i][j] == 0:
                print(2, i, j)
            else:
                path = get_path(i, j)
                print(len(path), *path)

 

정답코드는 위와 같다.

 

get_path() 함수가 나오기 전에는 일반적인 플로이드 알고리즘이다.

차이점이 있다면 위에서 말한 것처럼 parent 배열을 채우는 코드가 한줄 추가되었다.

 

get_path 는 위에서 말한대로 재귀적으로 경로를 구하는 함수이다.

이때 (a, k) (k, b) 에 대해서 구했을 때, 앞/뒤 경로를 모두 포함해서 구하도록 했는데, k 가 중복되므로 중복되는 k를 제거하기 위해서 뒷 경로를 앞 경로에 붙일 때 맨 앞의 k를 빼고 붙이도록 했다.