문제

풀이 과정

요약

플로이드 워셜 문제.

상세

1. 입력값을 받는다.

2. 이차원 배열을 만들고, 값을 초기화 한다. 최단 경로를 알아내는 문제이니, 초기에는 큰 값을 넣어두자. 단,출발점과 도착점이 동일한 경우, 즉 서로 동일한 장소를 가리키는 경우에는 이동할 필요가 없으니 당연히 0이다.

3. 버스의 값들을 입력해보자. 버스는 출발 도착이 여러 대 있을 수도 아닐 수도 있다. 입력값을 받을 때 마다 arr[i][j] 보다 작은 값인 경우에만 arr[i][j] 를 업데이트 한다.

4. 거쳐가는 구간을 기준으로, 모든 이동비용을 업데이트 한다. 현재 가지고 있는 $i$ → $j$ 로의 이동 비용이, $i$ → $k$ → $j$ 의 이동경로 보다 큰 경우, 현재의 $i$ → $j$ 의 이동 비용을 $i$ → $k$ → $j$ 의 비용으로 업데이트 한다.

5. 출력하면 된다. 단 문제에서 모든 경로가 이어진다고 주장한 것은 아니다. 모든 좌표를 다 탐색하여도 어떤 마을에는 도달하지 못하는 경우도 발생할 수 있다는 뜻 이다. 따라서 초기값인 INF 를 계속 가지고 있다면 이 값을 0 으로 출력해주어야 한다. (이동 자체를 할 수 없으므로 비용이 0 인거다)

정답

#include <bits/stdc++.h>
using namespace std;
int n, m, INF = 987654321;
int arr[101][101];

void print() {
    int ans;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            ans = arr[i][j] == INF ? 0 : arr[i][j];
            cout << ans << " ";
        }
        cout << "\n";
    }
}

void fw() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
            }
        }
    }
}

void init() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            arr[i][j] = i == j ? 0 : INF;
        }
    }

    int st, ed, v;
    for (int i = 0; i < m; i++) {
        cin >> st >> ed >> v;
        arr[st][ed] = min(arr[st][ed], v);
    }
}

int main() {
    init();
    fw();
    print();
    return 0;
}