[BOJ # 11404] 플로이드

주어진 문제는 위와 같다. 최대 100 개의 도시가 주어지고, 도시 간 이동이 가능한 버스 노선들이 주어졌을 때 모든 도시 간 이동 시의 최소 비용을 구하는 것이다. 최단 경로 탐색을 위한 알고리즘은 다익스트라, 벨만 포드, A* 탐색 등 여러 가지가 있지만 위와 같이 모든 노드 간 최단 경로를 구하기 위한 알고리즘으로 문제의 이름과 같은 플로이드 와샬 알고리즘이 있다.

 

플로이드 와샬 알고리즘에 대해 내가 기억하고 있는 것은, 노드 간 경로 가중치를 테이블에 저장하고 경로가 존재하지 않는 경우는 INF 값으로 저장한다. 그 뒤 스텝 별로 중간에 다른 노드를 경유하며 경로 가중치를 업데이트하는 방식으로 기억하고 있었다. 하지만 내가 기억하고 있는 알고리즘의 로직은 너무 모호해 문제 풀이에 적용할 수 없었고 따로 플로이드 와샬 알고리즘을 찾아본 뒤 문제를 해결했다.

 

플로이드 와샬 알고리즘

플로이드 와샬 알고리즘을 간단하게 설명하면, O(|V|^3) 의 시간 복잡도를 갖는 모든 쌍 최단 경로 탐색 알고리즘이다. 매 스텝 별로 X to Y (X, Y 는 노드) 경로의 가중치를 업데이트 해야 하므로 O(|V| ^ 2) 를 매 스텝 별로 실행하고, 각 스텝은 경유할 노드를 순차적으로 적용하므로 O(|V| ^ 2 * |V|) 의 시간 복잡도를 갖게 된다.

 

위의 그림을 통해, 알고리즘의 동작 방식을 설명할 수 있다. i, j 는 각각 노드 번호를 뜻하고 k 는 경유할 노드의 번호를 의미한다.

k = 0 일 때, 해당 테이블은 노드를 경유하지 않고 i - j 간 경로를 표현한 것이다.

k = 1 일 때, 변경된 table[2][3] 값은, 기존의 node(2) -> node(3) 의 경로 가중치는 3이고, 노드 1번을 경유한 node(2) -> node(1) -> node(3) 의 가중치 합이 4 + (-2) 이므로 새로운 값이 업데이트된 것을 볼 수 있다.

k = 2 일 때, node(4) -> node(1) 의 경로와 node(4) -> node(3) 의 경로가 2번 노드를 경유함으로 인해 가중치 값이 업데이트된 것을 확인할 수 있다.

---

이와 같이 경유할 노드를 변경해 가며 경로 가중치 값을 업데이트해 나가면 최종적으로 모든 노드 쌍 간의 최단 경로를 구할 수 있게 된다.

 

알고리즘을 적용한 코드는 3개의 for 문을 중첩함으로써 간단하게 구현이 가능하고, 이를 적용해 문제 해결에 사용한 코드는 다음과 같다.

 

#include <iostream>
using namespace std;

const int CITY = 100;
const int INF = 123456789;

int city, bus;
int dist[CITY + 1][CITY + 1];

void initialize() {
    for (int i = 1; i <= city; i++) {
        for (int j = 1; j <= city; j++) {
            dist[i][j] = INF;
        }
    }
}

void input() {
    cin >> city >> bus;
    initialize();

    for (int i = 0; i < bus; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = dist[a][b] < c ? dist[a][b] : c;
    }
}

void output() {
    for (int i = 1; i <= city; i++) {
        for (int j = 1; j <= city; j++) {
            if (dist[i][j] == INF) {
                cout << "0 ";
            } else {
                cout << dist[i][j] << " ";
            }
        }
        cout << "\n";
    }
}

void solve() {
    for (int k = 1; k <= city; k++) {
        for (int i = 1; i <= city; i++) {
            for (int j = 1; j <= city; j++) {
                if (i == j)
                    continue;
                int k_dist = dist[i][k] + dist[k][j];
                dist[i][j] = dist[i][j] < k_dist ? dist[i][j] : k_dist;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();

    solve();

    output();
}

 

# Reference.

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전