[11403] 경로 찾기 - 플로이드-워셜

플로이드 워셜 방법을 처음 써봤다.

 

플로이드-워셜(Floyd-Warshall) 알고리즘은 "모든 지점에서 다른 모든 지점까지의 최단 경로"를 구하는 알고리즘임. 다익스트라와 다르게 음수 간선이 있어도 동작한다는 특징이 있음. (단, 음수 사이클은 없어야 함)

---

1. 핵심 원리 (점화식)

거쳐가는 '중간 노드'를 기준으로 테이블을 갱신함.

"A에서 B로 가는 거리보다, A에서 거쳐가는 지점 K를 지나 B로 가는 거리가 더 짧으면 갱신한다!"

---

2. 파이썬 코드 예시

import sys

INF = int(1e9) # 무한대를 의미하는 값 (10억)

# 노드의 개수(n) 및 간선의 개수(m) 입력
n = int(input())
m = int(input())

# 2차원 리스트(그래프)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선 정보를 입력받아 그래프 채우기
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 핵심: 3중 for문 (거쳐가는 노드 k가 가장 바깥쪽!)
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            # 점화식: graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
            if graph[a][k] + graph[k][b] < graph[a][b]:
                graph[a][b] = graph[a][k] + graph[k][b]

# 결과 출력
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if graph[a][b] == INF:
            print("무한", end=" ")
        else:
            print(graph[a][b], end=" ")
    print()

---

3. 특징 정리

• 시간 복잡도: 3중 for문을 쓰기 때문에 O(n^3)임. 노드 개수(n)가 500개만 넘어가도 매우 느려지니 보통 n이 100~400 수준일 때 사용함.
• 자료구조: 2차원 리스트(인접 행렬)를 사용하여 모든 경로를 저장함.
• 알고리즘 분류: 그리디가 아니라 다이나믹 프로그래밍(DP)에 속함. (이전 단계의 최단 경로 정보를 이용해서 다음 정보를 갱신하기 때문임)

---

import sys

input = sys.stdin.readline

n = int(input())

gra = []

for i in range(n):
    li = list(map(int, input().strip().split()))
    gra.append(li)

for tmp in range(n):
    for frm in range(n):
        for to in range(n):
            if gra[frm][tmp] == gra[tmp][to] == 1:
                gra[frm][to] = 1
for i in range(n):
    for j in range(n):
        print(f"{gra[i][j]} ", end="")
    print()