[백준] 11404번 - 플로이드

---

문제 분석

모든 도시의 쌍과 관련된 최솟값을 구하는 문제이다.
그래프에서 시작점을 지정하지 않고, 모든 노드와 관련된 최소 경로를 구해야 하므로,
플로이드-워셜 알고리즘을 통해 해결하면 된다.
플로이드-워셜 알고리즘은 다음과 같다.

---

😊플로이드 워셜

💡 ✅ `최단 경로 탐색` ✅ `음수 가중치 허용` ✅ `동적 계획법의 원리 이용`

😊플로이드 워셜의 핵심이론

💡 `플로이드-워셜 알고리즘` 의 핵심적인 원리 A노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로이다.

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

---

😊플로이드 워셜 알고리즘 로직

💡 1. `리스트를 선언하고 초기화 하기`

D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 리스트라 정의한다.

S와 E의 값이 같은 칸은 0, 다른 칸은 sys.maxsize로 초기화 한다.

(S == E는 자기 자신에게 가는데 걸리는 최단 경로값을 의미하기 때문)

💡 2. `최단 거리 리스트에 그래프 데이터 저장하기`

S,E,W 를 각각 출발 노드, 도착 노드, 가중치라고 했을 때, D[S][E] = W로 에지의 정보를 리스트에 입력한다.

💡 3. `점화식으로 리스트 업데이트하기`

for 경유지 K에 관해 (1 ~ N)
	for 출발 노드 S에 관해 (1 ~ N)
		for 도착 노드 E에 관해 (1 ~ N)
			D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

---

소스 코드

# 플로이드

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
arr = [[sys.maxsize for j in range(N)] for i in range(N)]

for i in range(N):
    arr[i][i] = 0

for _ in range(M):
    s,e,w = map(int, input().split())
    if arr[s-1][e-1] > w:
      arr[s-1][e-1] = w

for K in range(N):
    for S in range(N):
        for E in range(N):
            arr[S][E] = min(arr[S][E], arr[S][K] + arr[K][E])

for i in range(N):
    for j in range(N):
        if arr[i][j] == sys.maxsize:
            print(0, end=' ')
        else:
            print(arr[i][j], end=' ')
    print()