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

문제 출처: https://www.acmicpc.net/problem/11780

11780번: 플로이드 2

플로이드 알고리즘으로 모든 쌍에 대해 최단거리를 구할 수 있다.

이 문제에서는 추가로 방문 경로를 구하여야 한다.

 

BFS같은 경우에서의 방문 경로는 prev 배열을 통해 a에서 b, b에서 c로 움직인 경우

prev[b] = a, prev[c] = b 으로 저장해두어 

도착지에서 출발지까지 역순으로 찾을 수 있다.

 

플로이드에서는

1에서 3으로 가는 비용 10이고 prev배열은 prev[1][3] = 1으로 저장해둔다.

1에서 2를 경유하여 3으로 가는 비용이 5 이면 prev[1][3] = 2로 저장해둔다. (prev[1][2]는 1로 초기화 되어있다.)

prev[1][3] = 2

prev[1][2] = 1

위와 같이 방문 경로를 구할 수 있다.

 

1,2,3,4,5 에서 [1][3] 은 1-2-3이 최단거리이고 [3][5] 는 3-4-5가 최단거리 이고 [1][5]를 구할 때

[1][5] = [1][3] + [3][5] 일 것이고 prev는 [1][5] = 3으로 저장될 것이다.

이때 [3][5]에 있는 4가 생략되어 버리는 문제가 있다.

따라서 재귀함수를 만들어 prev[start][end] = middle에서

start~middle 부분의 경로와 middle~end 부분의 경로를 분할하여 리턴하도록 한다.

 

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cstring>
#include<math.h>
#include<queue>
#include<vector>

using namespace std;

struct P{
	int y, x;
};

const int INF = 12345678;
int N, M;
int arr[101][101];
int visit[101][101];

vector<int> pathFind(int start, int end) {
	vector<int> path;
	int middle = visit[start][end];

	if (start == middle) {
		path.push_back(end);
		return path;
	}
	else {
		vector<int> head = pathFind(start, middle);
		vector<int> tail = pathFind(middle, end);

		for (int i = 0; i < tail.size(); i++) {
			head.push_back(tail[i]);
		}

		return head;
	}
}



int main(void)
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	fill(&arr[0][0], &arr[100][101], INF);

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		if (arr[a][b] != 0) {
			if (arr[a][b] < c)continue;
		}
		arr[a][b] = c;
		visit[a][b] = a;

	}

	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (k == i || k == j || i == j)continue;
				if (arr[i][k] + arr[k][j] < arr[i][j]) {
					visit[i][j] = k;
					arr[i][j] = arr[i][k] + arr[k][j];
				}

			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (arr[i][j] == INF) {
				cout << "0"<<" ";
			}
			else {
				cout << arr[i][j] << " ";
			}
		}
		cout << endl;
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (arr[i][j] == INF)cout << "0" << endl;
			else {
				vector<int> path = pathFind(i, j);
				

				cout << path.size()+1 << " ";
				cout << i << " ";
				for (int z = 0; z < path.size(); z++) {
					cout << path[z] << " ";
				}
				cout << endl;
				

			}
		}

	}

}