[알고리즘] 백준 11780번: 플로이드 2 (C++), 최단 경로 발생 노드 담기

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

11780번: 플로이드 2

이번 문제의 어려운 점은 아마 "i에서 j로 갈 때의 최단 경로에 속한 노드들"을 구하는 것이었다.

 

[시도 #1]

다익스트라에서 경로 역추적했던 것을 영감 삼아 해결해보려 했었다.

3차원 동적배열을 선언하여 i와 j에 k가 들어가면서 최단 경로가 갱신될 때마다 k를 push 했다.

if (graph[i][k] + graph[k][j] < graph[i][j]) {
	graph[i][j] = graph[i][k] + graph[k][j];
	trace[i][j].push_back(k);
}

그리고 출력할 때, i와 j사이에 있는 노드들을 모두 출력해주었다.

for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		if (i == j) cout << 0 << '\n';
		else {
			cout << trace[i][j].size() + 2 << ' ';
			cout << i << ' ';
			for (int k = 0; k < trace[i][j].size(); k++) {
				cout << trace[i][j][k] << ' ';
			}
			cout << j << ' ' << '\n';
		}
	}
}

 

사실상 이 코드는 코드의 흐름상 너무 이상하다. (아무래도 생각 없이 구현했던 거 같다.)

i와 j사이에 최단 거리, 노드 k는 하나가 들어있어야 하는데 여러 개를 갱신한다는 게 이상했다.

i와 j 사이에 노드가 2개 이상인 경우는 통하지도 않으며 간혹가다가 4개가 출력되어야 하는데 2~3개가 나오는 오류도 있었다.

 

[시도 #2]

i와 j 사이의 하나의 노드 k가 들어가는 것을 깨닫고, trace[i][j] = k (노드 i와 j 사이에는 노드 k가 있다는 뜻) 2차원 배열을 만들어 노드들을 담았다.

void floydWarshall() {
	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 (graph[i][k] + graph[k][j] < graph[i][j]) {
					graph[i][j] = graph[i][k] + graph[k][j];
					trace[i][j] = k;
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		graph[i][i] = 0;
	}
}

여기서 또 문제가 있었는데 "이 노드들을 또 어떻게 출력해낼지"가 관건이었다.

---

[솔루션: 참고했음]

구글링으로 비슷하게 접근한 솔루션들 중 하나를 찾았다. (https://yabmoons.tistory.com/441)

재귀를 통해 출력을 해주었는데 생각해낸 사람 진짜 천재다.

이 함수가 이번 문제의 핵심 포인트다.

void findPath(int start, int end) {
	if (trace[start][end] == 0) {
		path.push_back(start);
		path.push_back(end);
		return;
	}
	findPath(start, trace[start][end]);
	path.pop_back(); // end pop: 재귀 2번으로 인해 겹치는 노드 하나 삭제
	findPath(trace[start][end], end);
}

다익스트라나 플로이드 와샬에서 start에서 end로 갈 때 최단 경로를 발생시키는 정점들을 알아내는 방법들을 익혀두어야겠다.

다익스트라: 경로 역추적

플로이드 와샬: i,j 사이 노드를 재귀 함수로 구현

---

[AC 코드]

#include <iostream>
#include <vector>
#include <cmath>
#define MAX 100 + 1
#define INF 987654321
using namespace std;

int n, m;
int graph[MAX][MAX];
int trace[MAX][MAX];
vector<int> path;

void floydWarshall() {
	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 (graph[i][k] + graph[k][j] < graph[i][j]) {
					graph[i][j] = graph[i][k] + graph[k][j];
					trace[i][j] = k;
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		graph[i][i] = 0;
	}
}

void findPath(int start, int end) {
	if (trace[start][end] == 0) {
		path.push_back(start);
		path.push_back(end);
		return;
	}
	findPath(start, trace[start][end]);
	path.pop_back(); // end pop: 재귀 2번으로 인해 겹치는 노드 하나 삭제
	findPath(trace[start][end], end);
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			graph[i][j] = INF;
		}
	}

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

	floydWarshall();

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

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (graph[i][j] == INF || graph[i][j] == 0) cout << 0 << '\n';
			else {
				path.clear();
				findPath(i, j);
				cout << path.size() << ' ';
				for (int i = 0; i < path.size(); i++) {
					cout << path[i] << ' ';
				}
				cout << '\n';
			}
		}
	}

	return 0;
}

---

무조건 업 솔빙!