[C++] 백준 11404번: 플로이드

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

모든 노드 사이의 최소 비용을 구하여라.

---

시간복잡도 어림하기

 모든 노드 사이의 최소 비용을 구하는 알고리즘은 플로이드 워셜(Floyd-Warshall) 알고리즘 입니다. 플로이드 워셜 알고리즘은 O(n^3)의 시간복잡도를 가지는데, 문제에서 n의 최댓값은 100이므로 n^3 = 1,000,000 입니다. 이는 제한 시간 내에 문제를 해결하기 적절한 수치이므로 플로이드 워셜 알고리즘을 그대로 구현하면 되는 문제입니다. 

---

알고리즘 설계하기

 플로이드 워셜 알고리즘음 다음과 같이 동작합니다.

1. 최소 비용 배열 초기화
2. 노드 i, j, k에 대해 i에서 j로 이동하는 비용과 i에서 k를 경유하여 j로 가는 비용 중 최솟값을 최소비용으로 취함.

 이처럼 아주 간단한 로직으로 구성되어 있습니다.

 

 최소 비용 배열 초기화 단계에서는 우선 모든 최소 비용을 아주 큰 값인 INF로 초기화 하고, i에서 i로 이동하는 최소 비용을 0 이므로 자기자신으로 이동하는 최소 비용을 0으로 초기화합니다.

 

 최소 비용을 갱신하는 단계에서는 for 루프를 세 개 중첩하여 i에서 j까지 곧바로 이동하는데 드는 비용과 k를 경유하여 이동하는 비용을 서로 비교하여 그 중 작은 값을 최소 비용으로 취하면 쉽게 해결할 수 있습니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include <iostream>
#define INF 1e9
using namespace std;

int n, m, dist[104][104];
int main() {
    /*입출력 성능 향상*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    /*초기 최소 비용 배열 초기화*/
    fill(&dist[0][0], &dist[0][0] + 104 * 104, INF);
    for(int i = 1; i <= n; i++) dist[i][i] = 0;
    
    /*거리 정보 입력*/
    int from, to, weight;
    for(int i = 0; i < m; i++){
        cin >> from >> to >> weight;
        /*이미 경로가 존재하는 경우 작은 값을 비용으로 선택*/
        if(dist[from][to] > 0) dist[from][to] = min(dist[from][to], weight);
        else dist[from][to] = weight;
    }

    /*플로이드 워셜 알고리즘*/
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cout << (dist[i][j] == INF ? 0 : dist[i][j]) << " ";
        }
        cout << '\n';
    }
    return 0;
}

 이처럼 입력과 초기화 부분만 신경을 쓰면 플로이드 워셜 알고리즘은 아주 간단히 구현할 수 있습니다.

 

 위 코드에서 입력을 받을 때, 기존에 저장된 비용이 있는지 확인하는 이유는 문제에서 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다."라는 조건 때문입니다. 또한, 결과  출력시에 이동할 수 없는 위치일 때는 0을 출력하라고 했으므로 이 부분도 반드시 신경써야합니다.

---