BOJ 11780 - 플로이드 2

BOJ 11780 - 플로이드 2

“플로이드-워셜 알고리즘 경로 복원”

BOJ 11780 - 플로이드 2

문제 링크



#include <bits/stdc++.h>
typedef long long ll;
const int INF = 0x3f3f3f3f;
using namespace std;

int ans[102][102];
int nxt[102][102];
bool vis[102];
int n, m;

void    Floyd()
{
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (ans[j][k] > ans[j][i] + ans[i][k]) {
                    ans[j][k] = ans[j][i] + ans[i][k];
                    nxt[j][k] = nxt[j][i]; 
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (i != j)
                ans[i][j] = INF;
    }

    for (int i = 0; i < m; i++) {
        int p, c, m; cin>>p>>c>>m;
        ans[p][c] = min(m, ans[p][c]);
        nxt[p][c] = c;
    }

    Floyd();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (ans[i][j] == INF) 
                cout << 0 << ' ';
            else
                cout << ans[i][j] << ' ';
        }
        cout << '\n';
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j || ans[i][j] == INF) {
                cout << 0 << '\n';
                continue ;
            }
            vector<int> path;
            int st = i;
            while (st != j) {
                path.push_back(st);
                st = nxt[st][j];
            }
            path.push_back(j);
            cout << path.size() << ' ';
            for (int i = 0; i < path.size(); i++)
                cout << path[i] << ' ';
            cout << '\n';
        }
    }

    return 0;
}
  • 선수 학습으로 BOJ 11404 - 플로이드를 풀어보아야 한다. 플로이드는 주어진 그래프에서 모든 정점 쌍 사이의 최단 거리를 구하고 출력하는 문제인데 플로이드 2는 최단 거리를 출력하는 것에 이어 실제로 어떤 경로로 가야 하는지 까지를 출력하는 한 단계 더 나아간 문제라 볼 수 있다. 플로이드-워셜 알고리즘 자체로는 최단 거리만 알 수 있을 뿐, 실제 어떤 경로로 가야하는지는 알 수가 없다. 물론 경로 복원도 바킹독 플로이드 강좌에 아주 친절하게 잘 설명되어 있지만, 따로 다뤄본다.

(1) 각 정점 쌍의 최단 거리를 기록하는 ans 배열 외에, 각 정점에서 최단 거리로 가려면 당장 어느 정점으로 움직여야 하는지만을 기록하는 nxt 배열이 하나 더 필요하다. 개시 시 각 노드 간의 연결이 parent->child, weight로 주어졌을 때 ans 배열에는 거리(weight)를, nxt 배열에는 child 자체를 기록한다. nxt 배열은 그 정점에서 당장 이동하는 도착점을 가리키게 된다. 한번에 갈 수 없다면, 아무런 값도 기록되지 않은 채 넘어간다.

for (int i = 0; i < m; i++) {
    int p, c, m; cin>>p>>c>>m;
    ans[p][c] = min(m, ans[p][c]);
    nxt[p][c] = c; // 각 정점에서 최단 거리로 가려면 당장 어느 정점으로 움직여야
                   // 하는지 만을 기록하는 `nxt` 배열
}

(2) Floyd 알고리즘을 실행하게 되면, 최단 거리로 가기 위해 거쳐가야만 하는 정점이 갱신되는데 이때 갱신이 일어나는 경우 nxt 배열 또한 갱신한다. ans 배열에는 거리를, nxt 배열에는 중간 정점 자체를 기록한다.

void    Floyd()
{
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (ans[j][k] > ans[j][i] + ans[i][k]) {
                    // ans 배열에는 거리를 기록.
                    ans[j][k] = ans[j][i] + ans[i][k];
                    // 만약 갱신이 일어났다면, nxt 배열에는 중간 노드 자체를
                    // 찍어준다. 이 중간 정점은 최단 거리로 가기 위해 반드시
                    // 거쳐야만 하는 정점 그 자체이다.
                    nxt[j][k] = nxt[j][i]; 
                }
            }
        }
    }
}

(3) ans 배열을 출력한 이후 nxt 배열을 출력하는데 vector<int>에 경로를 추적하면서 push back하고, 이어서 출력한다. 그래프를 따라가는 것과 비슷한 것 같다.

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        // 자기 자신 노드일 경우, 혹은 갈 수 없는 경우 0 출력하고 continue
        if (i == j || ans[i][j] == INF) { 
            cout << 0 << '\n';
            continue ;
        }
        vector<int> path; // 경로를 기록할 vector<int> path;
        int st = i; // 시작 지점
        while (st != j) { // 도착할 때 까지 반복
            path.push_back(st); // 해당 지점을 push back
            st = nxt[st][j]; // 한번 갱신
        }
        path.push_back(j); // 도착 지점을 push back
        cout << path.size() << ' '; // size 출력
        for (int i = 0; i < path.size(); i++)
            cout << path[i] << ' '; // 정점 출력
        cout << '\n';
    }
}