[BOJ] 백준 11404 플로이드 c++ (플로이드-워셜)

문제 출처 : https://www.acmicpc.net/problem/11404

11404번: 플로이드

---

플로이드 워셜

플로이드 워셜 알고리즘을 사용하는 문제이다! 다익스트라와 플로이드-워셜의 차이는 아래와 같다.

다익스트라 : 하나의 정점에서 다른 모든 정점의 최단거리

플로이드 : 모든 노드간 최단거리

 

플로이드 알고리즘의 프로세스는 아래와 같다.

1. 인접 배열을 구한다.
2. 1번노드를 중간 노드(거쳐가는 노드)로 설정해, 거쳐가는 경우의 비용이 더 작으면 배열을 갱신한다.
3. n번노드까지 반복한다.

즉 시간복잡도가 O(n^3)이므로, 그래프 크기가 작아 시간 여유가 있을때 사용이 가능하다.

---

풀이

먼저 인접 배열을 구해야 한다!

여기서 주의할 점은 문제에서 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 라는 조건이 있다.

따라서 더 작은 비용인 경우에만 인접 배열을 업데이트 한다.

vector<vector<int>> dist(n+1, vector<int>(n+1, 987654321));
int a, b, c;

for(int i = 0; i < m; i++){
    cin >> a >> b >> c;
    if(dist[a][b] > c)
        dist[a][b] = c;
}

for(int i = 1; i <= n; i++)
    dist[i][i] = 0;

 

다음으로 1~n번 노드까지 중간 노드(거쳐가는 노드)로 설정해 비용을 비교해 업데이트 해야한다.

3중 for문을 돌려 기존 i~j 비용보다 i~k + k~j 비용이 작으면 업데이트 한다.

// k : 중간 노드
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]);
        }
    }
}

---

코드

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

using namespace std;

int n, m;

int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;

    vector<vector<int>> dist(n+1, vector<int>(n+1, 987654321));
    int a, b, c;

    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        if(dist[a][b] > c)
            dist[a][b] = c;
    }

    for(int i = 1; i <= n; i++)
        dist[i][i] = 0;
        
    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++){
            int ans = (dist[i][j] == 987654321? 0 : dist[i][j]);
            cout << ans << ' ';
        }
        cout << '\n';
    }
    return 0;
}