백준 11780번 플로이드 2 - C++ 풀이

---

 

1. 플로이드 와샬 알고리즘을 사용하여 모든 도시 쌍에 대해 최단 거리를 구한다.
2. 플로이드 와샬 알고리즘을 수행할 때 이전 방문 도시 before를 함께 기록한다.
3. before를 이용하여 시작 도시에서 도착 도시까지의 루트를 구한다.

 

1. 플로이드 와샬 알고리즘을 사용하여 모든 도시 쌍에 대해 최단 거리를 구한다.

 플로이드 와샬 알고리즘을 사용하여 O(N^3)에 모든 노드 쌍에 대해 최단 거리를 구할 수 있다.

 

2. 플로이드 와샬 알고리즘을 수행할 때 이전 방문 도시 before를 함께 기록한다.

 플로이드 와샬 알고리즘에서 i -> j로 가는 것보다 i -> k -> j로 k를 거쳐가는 것이 더 빠를 때 거리를 업데이트한다. i에서 j로 가는 길에 k를 방문하므로, i에서 j로 갈 때 이전 방문도시를 before[i][j] = k로 기록해둔다.

 

3. before를 이용하여 시작 도시에서 도착 도시까지의 루트를 구한다.

 시작도시 s에서 도착 도시 e까지 가는 루트는, s에서 before로 가는 루트 + before에서 e로 가는 루트이다. 이때 before가 겹치므로 before를 한번 빼준다.

반응형

---

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

using namespace std;

const int INF = 987654321;

int N, M;
int dist[101][101], before[101][101];

void FloydWarshall() {
    for (int k=1; k<=N; k++) {
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=N; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    before[i][j] = k;
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

vector<int> getRoute(int s, int e) {
    if (before[s][e] == s) return {s, e};
    
    vector<int> route;
    auto l = getRoute(s, before[s][e]);
    auto r = getRoute(before[s][e], e);
    
    for (auto node: l) route.push_back(node);
    route.pop_back();
    for (auto node: r) route.push_back(node);
    
    return route;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    for (int i=1; i<=100; i++) {
        for (int j=1; j<=100; j++) {
            dist[i][j] = (i == j) ? 0 : INF;
        }
    }
    
    cin >> N >> M;
    for (int i=0; i<M; i++) {
        int a, b, c; cin >> a >> b >> c;
        if (c < dist[a][b]) {
            dist[a][b] = c;
            before[a][b] = a;
        }
    }
    
    FloydWarshall();
    
    for (int s=1; s<=N; s++) {
        for (int e=1; e<=N; e++) {
            if (dist[s][e] == INF) cout << 0 << " ";
            else cout << dist[s][e] << " ";
        }
        cout << "\n";
    }
    
    for (int i=1; i<=N; i++) {
        for (int j=1; j<=N; j++) {
            if (dist[i][j] == INF || i == j) {
                cout << 0;
            }
            else {
                vector<int> route = getRoute(i, j);
                cout << route.size() << " ";
                for (auto node: route) cout << node << " ";
            }
            
            cout << "\n";
        }
    }

    return 0;
}