TIL - 2025.03.30 (일요일)

📝 오늘 배운 것 (플로이드 워셜 알고리즘)

플로이드 워셜 알고리즘

플로이드 워셜(Floyd_Warshall) 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 수해야 하는 경우 사용하는 알고리즘이다.

다익스트라 알고리즘에서 최단거리가 가장 짧은 노드를 탐색하는 과정을 생략할 수 있다.

모든 노드가 다른 노드로 가는 최단 거리 정보를 2차원 리스트에 저장한다. 노드의 개수 N만큼 점화식에 맞게 2차원 리스트를 갱신하는 다이나믹프로그램으로 볼 수 있다.

⏱️ 시간 복잡도

모든 최단 경로를 2차원 리스트에 담아 처리하기 때문에 매번 O(N^2)의 시간이 소요된다.

노드의 개수 N만큼 O(N^2)연산을 통해 해당 노드가 거치는 모든 경로를 고려한다.

현재 노드를 거쳐 지나가는 모든 경우를 찾기 위해, N-1 개의 노드 중 2개의 쌍을 선택하고 거리를 계산한다. 더 짧은 거리로 계산된다면 갱신한다.

전체적인 시간 복잡도는 O(N^3)이다.

🔤 플로이드 워셜 알고리즘 과정

하나의 정점에서 다른 정점으로 바로 갈 수 있으면 최소 비용을, 갈 수 없다면 INF로 배열에 값을 저장한다.
3중 for문을 통해 거쳐가는 정점을 설정한 후 해당 정점을 거쳐가서 비용이 줄여드는 경우에는 값을 바꿔준다.
위의 과정을 반복해 모든 정점 사이의 최단 경로를 탐색한다.

위와 같은 단방향 그래프가 있다면 정점은 1,2,3,4로 4개이다.

간선은 7개이다.

플로이드-워셜 알고리즘은 각각의 점들을 거치는 경우를 생각해야 한다.

0	2	INF	4
2	0	INF	5
3	INF	0	INF
INF	2	1	0

Dist는 1부터 각 정점까지의 최단 경로를 담는 배열이다.

0	2	INF	4
2	0	INF	5
3	5	0	7
INF	2	1	0

시작점과 끝점이 1을 거치는 경우에 값이 기존 값보다 작은 경우 최단 경로를 Dist에 넣는다.
3에서 2로 가는 방법이 INF였는데 3에서 1을 거쳐 2로 가는 방법이 5이기 때문에 Dist [3][2]는 5로 바꿔준다.
3에서 4로 가는 방법이 INF였는데 3에서 1을 거쳐 4로 가는 방법이 7이기 때문데 Dist [3][4]는 7로 바꿔준다.

0	2	INF	4
2	0	INF	5
3	5	0	7
4	2	1	0

4에서 1로 가는 방법이 INF였는데 2에서 4을 거쳐 4로 가는 방법이 4이기 때문에 Dist [4][1]는 4로 바꿔준다.

0	2	INF	4
2	0	INF	5
3	5	0	7
4	2	1	0

3을 거쳐가는 경우에 변동이 없다.

0	2	5	4
2	0	6	5
3	5	0	7
4	2	1	0

1에서 3로 가는 방법이 INF였는데 1에서 4를 거쳐 3으로 가는 방법이 5이기 때문에 Dist [1][3]는 5로 바꿔준다.
2에서 3로 가는 방법이 INF였는데 2에서 4를 거쳐 3으로 가는 방법이 6이기 때문에 Dist [2][3]는 6으로 바꿔준다.

0	2	5	4
2	0	6	5
3	5	0	7
4	2	1	0

🗓️ 예시 문제 (백준 11404 플로이드)

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

이 문제는 이름 부터 플로이드이다.

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

INF = int(1e18)
graph = [[INF] * (n+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = min(c, graph[a][b])

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])

for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print(0)
        else:
            print(graph[a][b], end=" ")
    print()

시작할 때 기본적인 2차원 리스트를 INF로 채워서 초기화한다.
첫 번째 이중 For문에서 대각선 방향으로 즉 자기 자신에 대한 값은 0으로 초기화한다.
이후 입력으로 받은 가중치 값을 그래프에 기록한다.
3중 For문을 수행하며 DP [a][b] = min(DP [a][b] , DP [a][k] + DP [k][b])를 수행한다.

🧐 느낀 점

이론을 이해하는데 오래 걸렸는데 막상 수행하고 보니 쉬운 알고리즘 같다.

📚 참고 자료

플로이드-워셜(Floyd-Warshall) 알고리즘 이론과 파이썬 구현

저작자표시 동일조건