[백준] 11780 - 플로이드 2

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

11780번: 플로이드 2

 

문제 이름에 나와있는 것처럼 플로이드를 활용해서 푸는 문제인데, 출력이 굉장히 길다.

처음 출력은 플로이드를 수행한 결과 배열을 출력하는 것이고,

다음부터는 모든 정점 쌍 i, j에 대하여 i에서 j로 가는 경로중, 최단 경로일 때 거치는 정점을 출력하는 것이었다.

 

처음 출력은 플로이드-와샬 알고리즘을 이용해서 해결할 수 있다.

하지만 뒷부분의 출력 때문에 이 알고리즘 수행 중에, 경로를 저장하는 행위를 해야 하는데,

이 포스트에 나와있는 대로 따로 배열을 만들어 최단거리를 만드는 경로를 저장할 수 있다.

 

그럼 이 경로 배열을 통해 출력을 완성해야 한다.

정점 i에서 정점 j로 최단 거리를 통해 갈 때 거치는 모든 정점을 출력해야 하므로, 재귀 함수를 하나 만들었다.

 

만약 정점 1에서 정점 4로 갈 때 최단 경로가 1 -> 2 -> 3 -> 4라고 하자.

그렇다면 1에서 4로가는 최단경로는, 1에서 route[1][4]로가는 최단경로 + route[1][4]에서 4로가는 최단경로가 될 것이다.

 

그래서 아래와 같이 go 함수를 작성하였다.

이때 ans.pop_back()을 한 이유는 route[s][e]가 중복되기 때문이다.

 

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

int n, m;
int map[101][101];
int route[101][101];

void go(int s, int e, vector<int>& ans) {

	if (route[s][e] == 0) {
		ans.push_back(s);
		ans.push_back(e);
		return;
	}
    
	go(s, route[s][e], ans);
	ans.pop_back();
	go(route[s][e], e, ans);
}

int main() {
	cin >> n >> m;

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

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

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

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j || !map[i][j])cout << "0 ";
			else {
            
				vector<int> ans;
				go(i, j, ans);
				cout << ans.size() << ' ';
                
				for (auto& k : ans) {
					cout << k << ' ';
				}
			}
			cout << '\n';
		}
	}

}