플로이드-와샬 알고리즘은 그래프에서 최단거리를 구하는 알고리즘 중 하나입니다. 플로이드 알고리즘, 플로이드-워셜 알고리즘 등으로 불리기도 합니다. 한 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 다른 최단거리 알고리즘과 다르게 모든 정점들 사이의 최단거리를 구할 수 있습니다. 정점의 수를 $V$라고 할 때 시간복잡도는 $O(V^3)$으로 꽤 높지만, 상수가 매우 작아 시간복잡도에 비해 빠르며 코드가 간단하다는 장점이 있어 모든 쌍 사이의 최단거리를 구하는 매우 효율적인 알고리즘입니다. 조금 응용하면 최단경로(최단거리인 경로에 속한 정점들) 또한 구할 수 있습니다.
편의를 위해 그래프의 정점의 개수를 $V$라고 부르겠습니다. 또한 이 글을 쉽게 읽으려면 그래프의 정점, 최단거리, 표현 방식 등 기초적인 그래프 이론에 대한 지식이 필요합니다.
알고리즘의 동작 방식
플로이드-와샬 알고리즘은 DP를 통해 정점들 사이의 최단거리를 계산합니다. 배낭 채우기 문제(Knapsack DP)와 비슷한 방식입니다. 모든 정점에 $1$번부터 $V$번까지의 번호를 붙이겠습니다. $1\sim N - 1$번 정점까지만 거쳐갈 수 있을 때의 최단거리를 알고 있으면 $N$번 정점까지 거쳐갈 수 있을 때의 최단거리 또한 알 수 있습니다. $N$번 정점이 추가되었을 때 최단경로는 $N$번 정점을 거쳐가는 새로운 경로이거나 $N - 1$번 정점까지만 거쳐가는 기존의 경로 중 하나입니다.
다시 말하면, 임의의 두 정점 A와 B에 대하여
- A에서 $N$번 정점까지 가는 최단거리 + $N$번 정점에서 B까지 가는 최단거리
- $1\sim N - 1$번 정점까지만 거쳐갈 때의 최단거리
둘 중 작은 값이 $1\sim N$번 정점까지만 거쳐갈 수 있을 때 A와 B까지의 최단거리가 됩니다. 따라서 모든 정점 쌍의 최단거리를 위와 같이 갱신한다면 $1\sim N$번 정점까지만 거쳐갈 수 있을 때 모든 정점들 사이의 최단거리를 구할 수 있습니다.
$D(N)$을 $1\sim N$번 정점까지만 거쳐갈 수 있을 때 모든 정점들 사이의 최단거리들이라고 정의하겠습니다. $D(0)$은 어떤 정점도 거치지 않는 최단거리들이므로 그래프의 초기 상태가 됩니다. $D(0)$에서 시작하여 $D(1)$, $D(2)$... 를 차례차례 구해 나가면 우리가 원하는 모든 정점 사이의 최단거리인 $D(V)$를 구할 수 있습니다.
임의의 $N$에 대해 $D(N)$을 구하려면 가능한 모든 정점 쌍 $V^2$개를 모두 검사해야 합니다. 이러한 과정을 $D(1)$부터 $D(V)$까지 $V$번 반복하므로 총 시간복잡도는 $O(V^3)$입니다.
코드
플로이드-와샬 알고리즘을 사용할 때는 인접 행렬을 이용하여 그래프를 표현해야 합니다. 인접 행렬로 표현된 그래프가 $D(0)$이 되기 때문입니다. 이차원 배열 dist로 그래프의 초기 상태를 표현합니다. 정점 A에서 정점 B로 가는 간선이 있다면 dist[A][B]는 해당 간선의 거리가 되며, A와 B가 연결되어 있지 않다면 dist[A][B]를 매우매우 큰 값으로 설정합니다. 이후 삼중 반복문을 통해 위에서 설명한 동작을 수행합니다.
- 가장 바깥 반복문은 경유점
- 내부의 이중반복문은 갱신할 정점
만 기억하면 코드를 쉽게 외울 수 있습니다.
가장 바깥 for문에서는 $i$가 $1$부터 $V$까지 순회하며 $D(i)$를 차례차례 구합니다. 각 $D(i)$를 구하는 과정에서 안쪽 이중 반복문을 통해 모든 정점의 쌍 $(j, k)$를 모두 검사하며 dist[j][k]를 갱신합니다.
만약 A에서 B로 가는 길이 있다면 매우매우 큰 값은 언젠가 최단거리로 갱신되겠지만, 길이 없다면 매우매우 큰 값이 그대로 남아 있게 됩니다. 이를 통해 두 정점을 잇는 경로의 존재 여부 또한 판단할 수 있습니다.
위 코드는 백준 11404번 문제의 정답 코드 중 일부입니다. 모든 정점 사이의 거리를 구해야 하고, 정점이 100개뿐이며, 문제 제목 또한 '플로이드' 인 것에서 알 수 있듯이 플로이드-와샬 알고리즘을 구현하면 되는 문제입니다.
전체 정답 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <cstdio>
#include <algorithm>
#define MAX 10000005
using namespace std;
int main() {
int dist[101][101], n, m, a, b, c;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j)
dist[i][j] = 0;
else
dist[i][j] = MAX;
}
}
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &a, &b, &c);
dist[a][b] = min(dist[a][b], c);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] == MAX)
printf("0 ");
else
printf("%d ", dist[i][j]);
}
printf("\n");
}
return 0;
}
|
cs |
최단 경로 구하기
위 코드를 약간만 수정하면 $O(V)$의 시간복잡도로 임의의 정점 A에서 B까지 최단거리로 이동할 때 거치는 정점들을 알 수 있습니다. 즉, 정점 A에서 B로 가는 최단경로를 구할 수 있습니다.
최단경로를 구하려면 최단경로에서 거치는 정점을 저장할 새로운 이차원 배열 via가 필요합니다. dist[j][k]값이 갱신될 때마다 via[j][k]또한 경유점인 $i$로 갱신해 줍니다. 이렇게 하면 삼중 반복문을 빠져나왔을 때 via[A][B]에는 정점 A에서 B로 가는 최단경로가 거치는 정점 중 하나가 저장되어 있게 됩니다. via[A][B]에 저장된 경유점을 N이라고 하면, A에서 B로 가는 최단경로는 A에서 N으로 가는 최단경로 + N에서 B로 가는 최단경로입니다. 따라서 재귀적으로 최단경로를 차례차례 구한다면 A에서 B로 가는 최단경로를 구할 수 있습니다.
최단경로는 최대 $V$개의 정점을 포함할 수 있으며, 최단경로를 탐색할 때는 최단경로에 속한 경유점들을 하나씩 살펴보게 됩니다. 따라서 시간복잡도는 $O(V)$입니다.
코드
플로이드-와샬 알고리즘을 수행하는 삼중 포문 안쪽에 via[j][k]를 갱신하는 코드가 추가되었습니다. 이를 바탕으로 재귀함수 find_path에서 최단경로를 구해줍니다. A부터 경유점 N까지의 경로와 N부터 B까지의 경로를 단순히 합치면 N이 두 번 들어가게 되기 때문에 중간에 N에 해당하는 정점을 한 번 빼 주어야 합니다. 위 코드는 백준 11780번 문제의 정답 코드 중 일부이며, 아래에서 코드 전체를 볼 수 있습니다.
전체 정답 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX 10000005
using namespace std;
int via[101][101];
vector<int> path;
void find_path(int i, int j) {
// i에서 j로 가는 최단경로 찾기
if (via[i][j]) {
// i와 j 사이의 경유점이 있음
find_path(i, via[i][j]);
path.pop_back();
find_path(via[i][j], j);
}
else {
// i와 j 사이의 경유점이 없음
path.push_back(i);
path.push_back(j);
}
}
int main() {
int dist[101][101], V, E, a, b, c;
scanf("%d%d", &V, &E);
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
if (i == j)
dist[i][j] = 0;
else
dist[i][j] = MAX;
}
}
for (int i = 0; i < E; i++) {
scanf("%d%d%d", &a, &b, &c);
dist[a][b] = min(c, dist[a][b]);
}
/* dist배열 초기화, 입력받기
v : 정점의 수 */
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
for (int k = 1; k <= V; k++) {
if (dist[j][k] > dist[j][i] + dist[i][k]) {
dist[j][k] = dist[j][i] + dist[i][k];
via[j][k] = i;
}
}
}
}
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
if (dist[i][j] == MAX)
printf("0 ");
else
printf("%d ", dist[i][j]);
}
printf("\n");
}
for (int i = 1; i <= V; i++) {
for (int j = 1; j <= V; j++) {
if (i == j || dist[i][j] == MAX)
printf("0\n");
else {
path.clear();
find_path(i, j);
printf("%d ", path.size());
for (auto i : path)
printf("%d ", i);
printf("\n");
}
}
}
return 0;
}
|
cs |
응용 문제
케빈 베이컨의 6단계 법칙
1389번: 케빈 베이컨의 6단계 법칙
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻
www.acmicpc.net
풀이
각각의 유저를 그래프의 정점으로, 친구 관계를 가중치가 1인 간선으로 생각할 수 있습니다.
정점이 최대 100개이므로 플로이드-와샬 알고리즘을 수행하면 각 유저의 케빈 베이컨 수를 알 수 있습니다.
백양로 브레이크
11562번: 백양로 브레이크
서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공
www.acmicpc.net
풀이
일방통행에서 양방향으로 고쳐야 하는 길의 수를 최소로 만들어야 합니다. 따라서 두 건물 사이의 거리를 고쳐야 하는 길의 개수로 정의하겠습니다.
건물 u에서 v로 가는 양방향 길이 있다면 u에서 v로, v에서 u로 가는 간선의 가중치는 모두 0입니다.
u에서만 v로 갈 수 있는 일방통행 길이 있다면 u에서 v로 가는 간선의 가중치는 0, v에서 u로 가는 간선의 가중치는 1입니다.
이렇게 만든 그래프에서 플로이드-와샬 알고리즘을 돌리면 모든 가능한 (u,v) 쌍에 대해 정답을 찾을 수 있습니다.
플로이드에 오타가?
13314번: 플로이드에 오타가?
평소에 코딩 실력이 부족하다고 느끼고 있는 지구이는 익명게시판에서 “백스페이스 키를 쓰지 않고 코딩하기를 추천합니다” 라는 글을 읽게 되었다. 글의 최하단에는 매우 작은 글씨로 “효
www.acmicpc.net
풀이
지구이의 코드는 k <= N이어야 하는 가장 바깥 for문의 조건문을 k < N으로 잘못 작성한 코드입니다. 이런 코드는 N번 정점을 지나는 최단경로를 찾아주지 못합니다. 따라서 정점이 100개이고 반드시 100번 정점을 지나야 최단경로가 되는 그래프를 자유롭게 만들어 출력하면 됩니다. 저는 100번 정점과 연결된 간선의 가중치는 모두 0으로, 나머지 간선의 가중치는 모두 1으로 만드는 전략을 사용했습니다.
'알고리즘&자료구조' 카테고리의 다른 글
| 세그먼트 트리 라이브러리 개발(C++) #1 (0) | 2021.08.03 |
|---|---|
| 세그먼트 트리 (0) | 2021.02.02 |
| 유니온 파인드 트리(분리 집합) (0) | 2021.02.02 |
| 트리 기초(의미, 구현, 용어, 종류) (0) | 2021.02.02 |
| 그래프 기초(의미, 분류, 구현 방법) (0) | 2021.02.02 |
