[BOJ] 백준 11404 - 플로이드

2021.08.09 - [Algorithm/Theory] - [Algorithm] Floyd-Warshall Algorithm(플로이드-와샬 알고리즘)

문제 링크

11404번: 플로이드

도시(정점), 버스(간선), 버스의 비용(가중치)를 갖는 그래프에서, 모든 도시(정점) 의 쌍 (A,B)에 대해 A에서 B로 가는데 필요한 최소 비용을 구하는 문제이다.

문제의 제목과 같이 Floyd-Warshall 알고리즘으로 해결 할 수 있었다.

해당 알고리즘은 아래 링크에서 확인할 수 있다.

2021.08.09 - [Algorithm/Theory] - [Algorithm] Floyd-Warshall Algorithm(플로이드-와샬 알고리즘)

[Algorithm] Floyd-Warshall Algorithm(플로이드-와샬 알고리즘)

 

기존의 다른 그래프 문제에서는 인접 리스트(Adjacency List)로 구현한 사례가 많았지만,

이번 문제에서는 정점의 수가 2개이상 100개 이하로 많지 않아 인접 행렬(Adjacency Matrix)로 구현했다.

#include <iostream>

#define INF 100000000
using namespace std;

int dist[101][101];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    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 = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = dist[a][b] < c ? dist[a][b] : c;
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    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;
}

위 소스코드에서 정점 i에서 정점 j로 가는 간선이 여러개 있을 수 있으므로

dist[a][b] = dist[a][b] < c ? dist[a][b] : c;

이 부분에서 가중치가 최소인 간선 하나만 택하도록 했다.