[BOJ/백준] 11780 플로이드 2

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()
def path(s,e):
    if next_node[s][e] == None:
        return [0]
    else:
        result = [s]
        while s != e:
            s = next_node[s][e]
            result.append(s)
        return result
N = int(input())
M = int(input())
INF = float('inf')
distance_list = [[0 if i==j else INF for j in range(N+1)] for i in range(N+1)]
 
next_node = [[None for _ in range(N+1)] for _ in range(N+1)]
graph = [{} for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    if distance_list[x][y] > pay:
        distance_list[x][y] = pay
        next_node[x][y] = y
 
 
for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if distance_list[start][end] > distance_list[start][mid] + distance_list[mid][end]:
                distance_list[start][end] = distance_list[start][mid] + distance_list[mid][end]
                next_node[start][end] = next_node[start][mid]
 
 
for i in range(1,N+1):
    print(*[val if val != INF else 0 for val in distance_list[i][1:]])
 
 
for start in range(1,N+1):
    for ends in range(1,N+1):
        if distance_list[start][ends] == INF:
            print(0)
        else:
            answer = path(start,ends)
            if len(answer) == 1:
                print(0)
            else:
                print(len(answer),*answer)

플로이드 와샬을 이용해서 풀어야하는데

 

여기서 중요한 점은 이동지점을 추적해야한다.

 

그 방법은 start-> end까지 갈때 들리는 노드를 갱신을 해주는 것이다.

 

a->b로 갈때 b로 간다고 저장을 해놨을때

 

중간에 값을 갱신한 mid가 있으면

 

a->b에 b가 아닌 mid를 저장해준다.

 

이렇게 함으로서

 

end_node가 동일한 것이 나올때까지 계속 반복을 해주면 되는 것이다.

 

플로이드 와샬은 자주 사용했지만, 경로를 구해본적은 처음이여서 힘들었다.

 

이 부분은 외우고 나중에 사용할 수 있도록 노력해야겠다.