[백준] 1719번 - 택배 (파이썬)

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

 

# 택배
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
arr = [[sys.maxsize] * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
    arr[i][i] = 0
for _ in range(m):
    x, y, cost = map(int, input().split())
    arr[x][y] = cost
    arr[y][x] = cost

result = [[j for j in range(n+1)] for i in range(n+1)]
for i in range(1, n+1):
    result[i][i] = '-'
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if arr[i][j] > arr[i][k]+arr[k][j]:
                arr[i][j] = arr[i][k]+arr[k][j]
                result[i][j] = result[i][k]

for line in result[1:]:
    print(*line[1:])

 

플로이드와샬
1. 인접 배열로 양방향 입력을 받는다. (자기 자신에서 자기 자신으로 가는 경우는 0, 나머지 무한)
2. result는 초기화할 때, j로 초기화 (자기 자신에서 자기 자신으로 가는 경우 '-')
3. 플로이드 와샬
    - i에서 j로 갈 때, k를 거쳐서 가는 경우가 더 작다면 그 값으로 초기화
    - result[i][j] = result[i][k] (가장 처음으로 거치고 간 노드의 값으로 계속 업데이트)
4. result를 슬라이싱 하여 각각 슬라이싱 값을 출력 (0번 인덱스는 제외)

 

최단거리 문제 → 출력 값을 보고 플로이드와샬을 생각 → n은 최대 200으로 O(n^3)의 시간 복잡도를 만족