문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

접근 과정

그래프의 모든 노드간의 최단 경로를 찾는 문제로 노드의 수가 적기 때문에 시간복잡도가 \(O(N^{3})\)인 플로이드 와샬 알고리즘으로 해결할 수 있는 문제이다. 풀이를 시작할 땐 몰랐는데 생각해보니 문제 이름이 그래서 플로이드… 대놓고 나와있었다.
구현이 어려운 알고리즘이 아니기 때문에 코드 작성은 금방 하였으나 알고리즘의 초기값 설정을 제대로 해주지 못한 부분이 있어 헤맸었다. 인접 행렬을 통해 플로이드 와샬 알고리즘을 구현할 때 연결되지 않은 노드들의 가중치를 임의의 큰 수로 설정주어야 한다. 근데 이 떄 값을 너무 크게 주어 계산 과정에서 오버플로우가 발생하기도 했고, 자기 자신에게 가는 경로의 가중치 또한 0으로 초기화하지 않았더니 다른 경로를 통해 다시 스스로에게 돌아오는 경로를 최단 경로로 인식하기도 했다. 여러모로 헤맨 끝에 통과.

소스 코드

#include <stdio.h>

#define MAX_COST 10000001

int main() {
    int N, M;
    int path[101][101];

    scanf("%d", &N);
    scanf("%d", &M);
    
    // 연결되지 않은 경로는 모두 임의의 큰 값으로 초기화
    for (int from = 1; from <= N; ++from) {
        for (int to = 1; to <= N; ++to) {
            path[from][to] = MAX_COST;
        }
    }
    for (int i = 1; i <= N; ++i) { path[i][i] = 0; }

    for (int i = 0; i < M; ++i) {
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        // 비용이 최소인 노선만을 취한다.
        if (path[from][to] > cost) { path[from][to] = cost; }
    }

    // 플로이드 와샬
    for (int mid = 1; mid <= N; ++mid) {
        for (int from = 1; from <= N; ++from) {
            for (int to = 1; to <= N; ++to) {
                int newCost = path[from][mid] + path[mid][to];
                if (path[from][to] > newCost) { path[from][to] = newCost; }
            }
        }
    }

    for (int from = 1; from <= N; ++from) {
        for (int to = 1; to <= N; ++to) {
            if (path[from][to] >= MAX_COST) { printf("0 "); }
            else { printf("%d ", path[from][to]); }
        }
        puts("");
    }
    return 0;
}