[백준 11780 파이썬] 플로이드 2 (골드 2, 플로이드 워셜)

알고리즘 유형 : 플로이드 워셜
풀이 참고 없이 스스로 풀었나요? : △

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline
INF = float("inf")

n = int(input())
m = int(input())
path = [[()]*(n+1) for _ in range(n+1)] # 최단 경로 리스트
APSP = [[INF]*(n+1) for _ in range(n+1)] # 최소 비용 리스트
for i in range(1, n+1):
    APSP[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    APSP[a][b] = min(APSP[a][b], c)
    path[a][b] = (a, b)
    
def floyd_warshall():
    for mid in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                cal_cost = APSP[i][mid] + APSP[mid][j]
                if cal_cost < APSP[i][j]:
                    APSP[i][j] = cal_cost
                    path[i][j] = path[i][mid] + path[mid][j][1:]
    return

floyd_warshall()

for i in range(1, n+1):
    line = []
    for j in range(1, n+1):
        if APSP[i][j] == INF:
            line.append(0)
        else:
            line.append(APSP[i][j])
    print(*line)

for i in range(1, n+1):
    for j in range(1, n+1):
        print(len(path[i][j]), *path[i][j])

풀이 요약

1. 플로이드 워셜 알고리즘에 역추적 로직만 섞어주면 되는 문제이다.

2. 먼저 플로이드 워셜로 최소 비용 2차원 리스트를 구한다.

   이 때, 모든 쌍에 대해 최단 경로 값을 구하여 전부 출력해야한다.

   따라서, 모든 쌍에 대한 최단 경로를 담을 2차원 리스트 path를 할당하고, 플로이드 워셜에서 갱신이 실행될 때, 최단경로 또한 i~중간 노드, 중간 노드~j의 합으로 갱신해준다.

3. 특히 주의할 점이라고 하면, 제자리 사이클을 0으로 초기화해주는 것과, 결과 값으로 구한 APSP 리스트에서 INF인 값을 만나면 0을 출력해주는 것 정도이다.

배운 점, 어려웠던 점

• 간선 정보를 APSP 리스트에 넣을 때, 같은 쌍에 대해 가중치만 다른 경우가 존재함을 간과하고, min 함수로 값을 넣어주는 걸 안해줘서 AC를 못 받았다. 플로이드 워셜 알고리즘 자체가 익숙하지 않았던 것 같다. 관련 문제를 더 많이 풀어봐야겠다.