[백준] 11780 플로이드2 - 플로이드 경로복원

[ 문제링크 ]

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

 

🚩 조건

1. 모든 도시의 쌍에 대해 필요한 비용의 최솟값을 구해라
2. 각 최솟값에 대해 경로를 구해라

 

 

🚩 접근

1 -> 플로이드 알고리즘 이용하자! (삼중for문 쓰면 됨)
2 -> 플로이드 알고리즘의 경로복원
       (nxt table 만들어서 경로 갱신 될 때마다 nxt도 갱신)

 

 

🚩 시행착오

 경로를 출력하는 방법에 대해 고민을 많이 했는데(재귀함수, while문 등등) 잘 안 풀렸다. 근데 방법의 문제가 아니라 nxt table을 보는 방법이 틀렸던 것이었다.ㅠ

 

 nxt table이 위와 같으면 2에서 1로 가는 경로는 아래와 같이 생각해야 한다.

nxt[2][1] = 4 (2에서 1로 최소비용으로 가려면 4를 거쳐야 함, 4로 이동)
-> nxt[4][1] = 5 (4에서 1로 최소비용으로 가려면 5를 거쳐야 함, 5로 이동)
-> nxt[5][1] = 1 (5에서 1로 최소비용으로 가려면 1로 바로 가야 함, 도착!)

 즉, nxt[i][j]==j 가 될 때 까지 nxt의 시작도시를 업데이트 하면 된다.

 

💻 코드 (C++)

#include <iostream>
#include <vector>
#define INF 100000000
using namespace std;

int table[101][101];
int nxt[101][101];
int cnt = 2;
vector<int> path;

int main() {
	for (int i = 1; i <= 100; i++) {
		for (int j = 1; j <= 100; j++) {
			table[i][j] = INF;
		}
	}
	int n, m, a, b, c;
	cin >> n >> m;

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

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) {
					table[i][j] = 0;
					continue;
				}
				if (table[i][j] > table[i][k] + table[k][j]) {
					table[i][j] = table[i][k] + table[k][j];
					nxt[i][j] = nxt[i][k];
				}
			}
		}
	}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (table[i][j] >= INF) {
				cout << 0;
			}
			else {
				cout << table[i][j];
			}
			cout << " ";
		}
		cout << "\n";
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (nxt[i][j] == 0) {
				cout << 0 << "\n";
				continue;
			}
			path.push_back(i);
			int st = i;
			while (nxt[st][j] != j) {
				cnt++;
				path.push_back(nxt[st][j]);
				st = nxt[st][j];
			}
			path.push_back(j);
			cout << cnt << " ";
			for (int k = 0; k < path.size(); k++) {
				cout << path[k] << " ";
			}
			path.clear();
			cnt = 2;
			cout << "\n";
		}
	}
}