BaekJoon 11780번 : 플로이드 2 (python)

BaekJoon 11780번 : 플로이드 2 (G2 45.511%)

플로이드 2 문제

플로이드 워셜 알고리즘을 이용해 최단경로를 구하고 해당 최단경로를 역추적 하는 문제이다.

• 플로이드 워셜 알고리즘 자체를 구현하는 것은 어렵지 않았다. a부터 b까지 다이렉트로 가는 값과 k를 거쳐 가는 값을 비교해가며 더 작은 값으로 업데이트를 하면 되는 문제이기 때문이다.
• 추가로 주어진 역추적 조건에서는 모든 경로의 역추적 경로를 출력해야하기 때문에 값이 업데이트 되는 부분에서 항상 거쳐가는 구역을 업데이트 해야한다.
• 문제는 distance가 업데이트 되는 부분인데 이 부분에서 원래는 a에서 b로 다이렉트로 갔었지만 그것보다 더 빠른 방법이 있기에 distance[a][k] + distance[k][b]로 업데이트가 된다. 이 때 a에서 b로 가는 position[a][b]는 position[a][k]를 담아서 [a][b]가기전 k를 경유한다는 의미로 이전의 값을 넣어주게 된다.
• 출력 부분에서는 i부터 j까지 이동하는 경우 position[i][j]의 값은 i에서 j로 가기전에 경유한 index를 담고 있게 된다. 이후로 해당 index에서 다시 j로 가기 위한 값을 계속 update해주다가 해당 index가 j가 됐을 때 도착한 것으로 간주하고 역추적이 마무리 된다.

느낀점

뭔가 오랜만에 풀어보는 플로이드워셜 알고리즘이라 기본폼을 사용하는데도 시간이 조금 소요된 것 같다.
간단한 다익스트라 알고리즘의 역추적과 달리 플로이드워셜 알고리즘의 역추적은 조금 이해하기 힘든 감이 없지 않아 있다. 아마 플로이드 워셜 알고리즘의 자세한 작동방식을 대충이나마 알고있지만 깊숙하게 알지 못해서 그렇지 않을까 싶은 생각이 든다. 이 부분에 관해서는 조금더 자세하게 공부해 볼 필요가 있다.

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
distance = [[float('inf')]*(n+1) for _ in range(n+1)]
position = [[None]*(n+1) for _ in range(n+1)]
for i in range(1,n+1) :
    distance[i][i] = 0

for _ in range(m) :
    a, b, c = map(int,input().split())
    if distance[a][b] > c :
        distance[a][b] = c
        position[a][b] = b

for k in range(1,n+1) :
    for a in range(1,n+1) :
        for b in range(1,n+1) :
            if distance[a][b] > distance[a][k] + distance[k][b] :
                distance[a][b] = distance[a][k] + distance[k][b]
                position[a][b] = position[a][k]

for i in range(1, n+1) :
    for j in range(1, n+1) :
        if distance[i][j] == float('inf') :
            print(0, end = ' ')
        else :
            print(distance[i][j],end=' ')
    print()
    
for i in range(1, n+1) :
    for j in range(1, n+1) :
        if i == j or distance[i][j] == float('inf'):
            print(0)
        else :
            start = i
            end = j
            path = [start]
            while start != end :
                start = position[start][end]
                path.append(start)
            print(len(path), *path)