[BOJ, C++]#11780_플로이드 2, 플로이드-워셜, 전체-쌍 최단 경로, 최단 경로 상의 정점 목록

#1. 문제

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

 

---

 

#2. 풀이

 

1. 플로이드-워셜(Floyd-Warshall)

[알고리즘]#2_길 찾기 알고리즘

플로이드-워셜은 최단 경로 알고리즘으로 그래프의 전체-쌍 최단 경로를 찾는 알고리즘입니다. 플로이드-워셜 알고리즘은 총 3개의 중첩 for문을 통해 구현되며, 최악의 시간 복잡도는 O(n³)입니다. 주로, 플로이드-워셜은 주어진 문제에서 '경유 정점' 개념이 강조될 때 활용합니다.

 

2. 플로이드-워셜 중 최단 경로를 이루는 정점들을 기억한다!

1. 모든 도시에 대하여 전체-쌍 최단 경로 값을 찾기 위해, 플로이드-워셜 알고리즘을 활용합니다.
2. 기존의 플로이드-워셜 알고리즘에 더해, 최단 경로 값 업데이트 시 i -> j 경로상에서 i 다음으로 방문할 정점 k를 기억해 줍니다.
3. 마지막으로, 한 정점에 대하여 다른 모든 정점으로 가는 최단 경로 값을 출력하고, while 룹을 통해 i = next [i][j] 방식으로 i -> j의 최단 경로 상에 위치한 도시 목록을 출력해 줍니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/11780
*   @문제: 플로이드 2
*   @설명
        1. 플로이드-워셜, 전체-쌍 최단 경로 찾기
        2. 최단 경로 상에 위치한 도시 목록 및 도시 개수 찾기
        3. 주목할 점: 최단 경로 상 도시 목록을 찾는 방법 주목
*/


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 101
#define INF 1e9

int n, m;
int graph[MAX][MAX];
int nxt[MAX][MAX];

//@플로이드-워셜 알고리즘 수행
void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (graph[i][k] + graph[k][j] < graph[i][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                    nxt[i][j] = nxt[i][k];
                }
            }
        }
    }
}

//@경로 재구성 함수
vector<int> getPath(int i, int j) {
    vector<int> path;
    if (nxt[i][j] == 0) return path;

    path.push_back(i);
    while (i != j) {
        i = nxt[i][j];
        path.push_back(i);
    }
    return path;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //@도시의 개수와 버스의 개수 입력
    cin >> n >> m;

    //@그래프 초기화
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i != j) graph[i][j] = INF;
        }
    }

    //@버스 정보 입력, a <-> b의 최단 경로에서 a 도시 다음으로 오는 도시를 b로 설정
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a][b] = min(graph[a][b], c);
        nxt[a][b] = b;
    }

    //@플로이드-워셜 알고리즘 수행
    floyd();

    //@최단 거리 출력
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cout << (graph[i][j] == INF ? 0 : graph[i][j]) << " ";
        }
        cout << "\n";
    }

    //@경로 정보 출력
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j || graph[i][j] == INF) {
                cout << "0\n";
            } else {
                vector<int> path = getPath(i, j);
                cout << path.size() << " ";
                for (int city : path) {
                    cout << city << " ";
                }
                cout << "\n";
            }
        }
    }

    return 0;
}

 

---