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

문제

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

---

문제 요약

n개의 도시가 있다.

 

한 도시에서 다른 도시에 도착하는 m개의 버스가 있다.  각 버스는 한 번 사용할 때 필요한 비용이 있다.

 

모든 도시의 쌍에 대해 도시 A에서 B로 가는데 필요한 비용의 최솟값을 출력한다.

 

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

---

코드

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

#define INF 1e9
using namespace std;

int n, m;

int dist[110][110];

vector<tuple<int, int>> edges[110];

int main() {
    cin >> n >> m;

    // 그래프 입력
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        edges[a].push_back({ b, w });
    }

    // dist 배열 초기 설정
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = INF;
        }
    }

    // 주어진 간선만 반영
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < edges[i].size(); j++) {
            int b, w;
            tie(b, w) = edges[i][j];

            dist[i][b] = min(dist[i][b], w);
        }
    }

    // i번 도시에서 k번 도시를 거쳐 j번 도시로 가는 비용 탐색
    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++) {
            if (dist[i][j] == INF) cout << 0 << " ";
            else cout << dist[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

---

코드 설명

플로이드 워셜 알고리즘으로 문제를 해결한다.

 

1. 벡터 edges에 그래프 정보를 인접 행렬로 입력 받는다.

 

2. dist 배열의 초기값을 설정한다.

+ i에서 i로 가는 거리는 0, 나머지는 무한대(INF)로 설정한다.

 

3. 주어진 간선 하나씩만 dist 배열에 반영한다.

+ 예를 들어 a에서 b로 가는 간선이 있다면, dist[a][b]에 가중치 w를 저장한다.

 

4. i번 도시에서 k번 도시를 거쳐 j번 도시로 가는 비용과 최소값을 모두 비교하여 갱신한다.

(반복문의 순서가 k, i, j임에 유의한다.)

---

고찰

모든 지점에서 모든 지점으로의 최단 거리를 구하기 위해서는 플로이드 워셜 알고리즘을 사용해야 한다.

 

다익스트라의 경우, 한 지점에서 다른 지점으로 가는 최단 거리만 제공하기 때문에 각 지점에 대해 한 번씩 다익스트라를 진행해야 한다.