플로이드 와샬 알고리즘 :: 마이구미

이번 글은 플로이드 와샬 알고리즘에 대해 다뤄본다.

동적계획법을 기반으로 구현되는 알고리즘이다.

위키백과의 정의를 보자.

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다.

정의를 보다시피 최단 경로를 찾기에 좋은 알고리즘이다.

시간복잡도는 3개의 반복문을 통해 O(n^3) 이다.

플로이드 알고리즘은 3개의 반복문이면 구현된다.

코드를 보면 굉장히 짧고 간단하다.

for (int k = 0; k < N; ++k) {

    for (int i = 0; i < N; ++i) {

        for (int j = 0; j < N; ++j) {

            if (d[i][j] > d[i][k] + d[k][j]) {
                d[i][j] = d[i][k] + d[k][j];
            }

        }
    }
}

굉장히 간단하지만, 반복문이 2개가 넘어갔기 때문에 이해가 어려울 수 있다.

먼저, 알고리즘 분석에 앞서 선행으로 구현해야할 것을 보자.

선행 조건으로는 2차원 배열 d에는 두 정점 간의 비용이 초기화 되어 있어야한다.

두 정점 간의 연결이 없다면 무한대로 초기화한다.

무한대로 초기화하는 이유는 이 무한대를 이용하여 두 정점간의 연결 여부를 파악하기 위해서다.

d 배열의 값이 무한대가 아니면 두 정점이 연결되어 있다는 의미이다.

무한대를 넣는 이유는 아래 플로이드 알고리즘의 반복문 내부에 존재하는 조건문을 보면 알 수 있다.

활용 사례는 두 정점간의 연결 여부에도 이용되고, 갱신여부에도 이용하게 된다.

플로이드 알고리즘을 이해하면 쉽게 이해될테니 다음으로 넘어가자.

for(int i=1;i<=n;i++) {

    for(int j=1;j<=n;j++) {

        d[i][j] = (i == j) ? 0 : ∞(문제에서의 최대값);

    }

}

d 배열에 주어진 정점 간의 비용을 넣어주게된다. (대부분 같은 정점끼리는 주어지지 않기 때문에 0을 초기화)

그 후 그래프 구현을 위한 인접 배열을 만들어준다.

for (int i = 1; i <= m; i++) {
    int v1 = sc.nextInt();
    int v2 = sc.nextInt();
    int cost = sc.nextInt();

    // 단방향 그래프
    d[a][b] = cost;

    // 양방향 그래프
    // d[a][b] = cost;
    // d[b][a] = cost;
}

플로이드 알고리즘을 위한 연결된 두 정점간의 비용이 초기화된 d 배열이 셋팅되었다.

그 후 플로이드 알고리즘을 통해 최단경로를 구하면 된다.

플로이드 알고리즘의 각각의 반복문을 역할을 알아보자.

위키의 정의대로라면 아래와 같다.

첫번째 반복문 - 거쳐가는 정점.

두번째 반복문 - 출발하는 정점.

세번째 반복문 - 도착하는 정점.

세번째 반복문에 존재하는 조건문만 이해하면 플로이드 알고리즘을 이해할 수 있다.

if (d[i][j] > d[i][k] + d[k][j]) {
    d[i][j] = d[i][k] + d[k][j];
}

위에서 말했듯이, k는 거쳐가는 정점, i는 출발하는 정점, j는 도착하는 정점이 된다.

예를 들어 1->4의 최단 경로를 보자.

위와 같이 만약 K가 4라고 한다면, d[1][4]는 총 4번 루프를 돌게 된다.

루프를 돌때마다 거쳐가는 정점(K)이 바뀌면서 갱신되게 된다. 

(갱신된다는 것은 경유지를 거쳐서 두 정점이 연결됐거나 경유지를 거치지 않고 연결된 거리가 최단 경로라는 뜻이다.)

K가 2일 경우 1->2의 경로 + 2->4의 경로를 더한 결과가 기존의 값보다 작을 시 갱신한다.

K가 3일 경우 1->3의 경로 + 3->4의 경로를 더한 결과가 기존의 값보다 작을 시 갱신한다.

이렇게 모든 경로를 확인함으로써, d 배열에는 정점 간의 최단 경로가 구해질 수 밖에 없다.

같은 정점이나 연결되지 않은 경우는 걱정할 필요가 없다.

위에서 같은 정점은 0으로 초기화하였고, 연결되지 않은 경우는 무한대로 초기화 되어있기 때문이다.

주의할 점은 문제에 따라 d 배열 셋팅이 달라질 수 있다.

양방향 그래프일 수도 있고, 단방향 그래프 일 수도 있다.

또한, 문제마다 무한대 값의 기준이 달라질 수 있다.

문제에 따라 d 배열만 셋팅한다면 최단 경로를 구하는 것은 똑같이 이용해도 문제 없다.

구한 최단 경로를 바탕으로 문제들을 해결하는 법이 달라질 뿐이다.

2660번 회장뽑기, 1956번 운동, 1613번 역사, 10159번 저울, 1238번 파티, 1389번 케빈 베이컨의 6단계 법칙 등등 많은 문제를 쉽게 풀 수 있다.

자세한 건 Github 을 통해 확인하자.

플로이드 관련 문제 소스 Github URL

https://github.com/hotehrud/acmicpc/tree/master/algorithm/Floyd