FWA 1부: 플로이드-워셜 알고리즘과 주의사항 (반복문의 순서가 중요한 이유)

플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 노드들 간 최단 경로를 찾는 알고리즘이다.

 

일단적으로 노드 N개와 두 노드를 잇는 간선 K개가 주어지고, 특정 두 노드를 잇는 최단 거리를 찾아야 하는 상황이 주어진다.

이럴 때는 다익스트라 알고리즘을 쓰면 된다.

 

다익스트라(데이크스트라) 알고리즘(Dijkstra Algorithm)은 두 노드 간 최단 경로를 찾는 알고리즘이다.

 

플로이드 워셜 알고리즘은 언제 쓰느냐?

가능한 모든 두 노드들 사이 최단 거리를 구할 때 쓴다.

 

그러니까 하나만 구하면 될 때는 다익스트라, 모두 구해야 할 때는 플로이드 워셜을 쓴다.

 

다익스트라 알고리즘의 시간 복잡도는 O(KlogK)이고 플로이드 워셜의 시간복잡도는 O(N^3)이다.

https://www.acmicpc.net/problem/11404 처럼 지도 하나에 대해 X가지 경우의 최단 거리를 구해야 할 때는 다익스트라 알고리즘을 X번 쓰는 것보다 플로이드 워셜을 한 번 쓰는 게 효율적이다.

 

 

---

n개의 노드가 있을 때 (n<100)

int d[100][100];

이라는 배열을 만들었다 해보자. d[a][b]의 값에 a번 노드에서 b번 노드로 가는 최단 거리를 넣는 게 목표이다.

 

플로이드 워셜 알고리즘의 구현 아주 간단한데, 바로 이렇다.

    for(int x=0;x<n;x++)
    {
        for(int a=0;a<n;a++)
        {
            for(int b=0;b<n;b++)
            {
                d[a][b]=min(d[a][b],d[a][x]+d[x][b]);
            }
        }
    }

초기의 d[][]배열에는 간선들의 정보가 저장되어 있다. 즉, d[a][b]의 값은 a과 b 노드가 간선으로 연결되어 있으면 그 간선의 비용 값이, 연결되어있지 않다면 무한대(또는 매우 큰 수)로 저장될 것이다.

지도가 이렇게 생겼다고 가정해보자. 그럼 d[][]배열은 초기 상태에 다음과 같을 것이다.

	0	1	2	3
0	0	3	4	5
1	3	0	∞	2
2	4	∞	0	∞
3	5	2	∞	0

 

이제 모든 노드를 순회할 것인데, 매번 그 노드(x라고 지칭하자)에 대해서 다음과 같은 작업을 수행한다:

 

모든 a, b에 대하여 d[a][b]와 d[a][x]+d[x][b]를 비교해 더 작은 값을 d[a][b]에 저장한다

 

d[a][x]+d[x][b]는 a에서 x까지 이동한 후, x에서 b까지 이동할 때 발생하는 비용이다. 즉, x를 경유해서 가는 경로의 비용이다. 

 

x=0일 때를 보자.

d[a][b]는 a와 b 사이 간선이 있다면 간선의 비용이고, 없다면 무한대이다. 

이게 무슨 뜻이냐면, a에서 b까지 가는 동안 곧바로만 가야지, 다른 노드를 경유해서 가면 안된다는 뜻이다.

그런데 위의 작업을 수행한 결과, 0번 노드를 경유해서 가는 것은 허용했을 때 최단 거리를 구할 수 있다.

 

x=1일 때의 작업을 수행한다면, 0번 노드와 1번 노드를 경유해서 가는 것을 허용했을 때 최단 거리가 d[][]배열에 저장된다.

 

....

....

 

x=3일때까지 작업을 수행하면, 0번 노드, 1번 노드, 2번 노드, 3번 노드 전부 다 경유하는 것이 허용된다.

그렇게 모든 a와 b에 대해 둘을 잇는 최단 거리를 구할 수 있다.

 

 

---

주의할 점!! - 반복문의 순서는 중요하다.

 

    for(int x=0;x<n;x++)
    {
        for(int a=0;a<n;a++)
        {
            for(int b=0;b<n;b++)
            {
                d[a][b]=min(d[a][b],d[a][x]+d[x][b]);
            }
        }
    }

위에서 코드로 구현한 부분을 다시 가져와보았다.

중요한 것은 for문의 순서이다.

x를 순회하는 for문이 가장 바깥에 있어야 한다는 게 아주 중요하다. 그렇지 않으면 구현이 잘못된다.

 

x=0일때 구해진 "0번 노드를 경유하는 것이 허용된 상황에서 최단 거리"가 x=1일 때 "0번 노드와 1번 노드를 경유하는 것이 허용된 상황에서 최단 거리"를 구하는 데에 이용되기 때문이다.

 

그렇기 때문에 "0번 노드를 경유하는 것이 허용된 상황에서 최단 거리"들을 전부 구한 그 다음 "0번 노드와 1번 노드를 경유하는 것이 허용된 상황에서 최단 거리"를 구해야 하는 것이다.

 

만약에 플로이드 워셜 알고리즘으로 백준 제출을 했는데 중반 정도에서 틀렸다면 구현의 실수를 생각해보자. 반복문의 순서가 흔히들 틀리는 이유일 것 같다.

---

이 알고리즘을 개발한 로버트 플로이드는 몇 년 뒤 공로를 인정받아 1978년에 튜링상을 수상했다.

 

 

플로이드 워셜 알고리즘은 최단 비용 경로의 비용을 구하는 알고리즘인데, 다음 글에서는 그 최단 경로 자체를 구하는 방법에 대하여 글을 써보도록 하겠다.