[C/C++] 백준 11780번 - 플로이드 2

✏️ 문제 링크

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

11780번: 플로이드 2

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

기본적인 플로이드 와샬 구현 문제에서 경유지의 개수와 경유지를 출력하는 문제입니다.

이런 경우에는 방문배열을 하나 더 만들어서 각 경로들의 마지막 경유지를 저장해주어야 합니다.

만약 예를 들어서 1->4의 경로가 있다면 route[1][4] = 1; 이런 식으로 말이죠

그렇게 다 저장을 해주게 되면은 

이런식으로 route배열이 저장됩니다. 예를 들면 route[5][2]의 마지막 경유지는 5이라는 의미를 가지고 있습니다.

이런 route배열을 재귀함수를 통해서 계속해서 경유지를 추적하면서 path배열에 추가하고 출력합니다.

만약 도착할 수 없다면 0을 출력합니다.

 

 

✏️ 문제 코드

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

int n, m, u, v, cost;
int map[101][101];
int route[101][101];
vector<int>path;
void pathfind(int start, int end);
int main() {

	ios::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)
				map[i][j] = 0;
			else
				map[i][j] = INF;
		}
	}

	while (m--) {
		cin >> u >> v >> cost;
		map[u][v] = min(map[u][v], cost);
		route[u][v] = u;
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (map[i][j] > map[i][k] + map[k][j]) {
					map[i][j] = map[i][k] + map[k][j];
					route[i][j] = route[k][j];
				}
			}
		}
	}

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

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				cout << 0 << "\n";
			else {
				pathfind(i, j);
				if (path.empty() && map[i][j] == INF)
					cout << 0 << " ";
				else {
					cout << path.size()+1 << " ";
					for (int i = 0; i < path.size(); i++) {
						cout << path[path.size() - i - 1] << " ";
					}
					cout << j << " ";
				}
				cout << '\n';
			}
			path.clear();
		}
	}
}
void pathfind(int start, int end) {
	int s = route[start][end];
	while (s != 0) {
		path.push_back(s);
		s = route[start][s];
	}
}

 

 

 

✏️ 참조

https://cocoon1787.tistory.com/468

[C/C++] 백준 11780번 - 플로이드 2 (플로이드 와샬)

이분 껄 참조했습니다.

 

 

✏️ 알게 된 점

경로를 추가하거나 경유지를 기록하는 것에 있어서는 추가적으로 방문 배열을 만들어서 가장 마지막 경유지를 저장하고

재귀함수를 통해서 경로를 출력할 수 있다