[BOJ] 택배 1719번

정리

이번 문제는 플로이드-와샬을 사용해서 풀었습니다. 전에 3문제 정도 플로이드-와샬과 관련된 문제를 전에 풀어봤었는데 그래서인지 다익스트라보다는 조금 더 친숙한 감이 있기도 했고, 경로표의 형태를 보니까 플로이드-와샬로 풀어도 무방할 것 같았습니다.

다른 건 괜찮았는데 마지막에 조금 헤맸던 부분이 1->2->5->6과 같이 2개 이상의 노드를 거쳐서 갔을 때 최단거리가 나오는 부분이었는데요. 처음에 짰던 코드로 돌렸을 때에는 2가 아닌 계속 5(도착 노드 바로 전 노드)가 나왔습니다. 

어떤 식으로 접근을 해야 할지 감이 잡히지 않아서 이 부분 풀이를 참고했는데, road 배열(최단 경로를 가기 위해 처음 방문하는 노드를 담은 배열)의 경우 [i][k]를 구해주면 최단거리로 가기 위해서 제일 처음 방문하는 정점을 담고 있다는 것을 알 수 있었습니다. 

소스코드

#include <iostream>

using namespace std;

#define INF 987654321

int arr[202][202];
int road[202][202];
int n, m;

void floyd() {
	//k : 거쳐가는 좌표
	for (int k = 1; k <= n; k++) {
		//i : 처음 좌표
		for (int i = 1; i <= n; i++) {
			// j : 도착 좌표
			for (int j = 1; j <= n; j++) {
				if (i == j || i == k || k == j) continue;
				if (arr[i][j] > arr[i][k] + arr[k][j]) {
					// i->j로 가는 것보다 i->k->j가 더 가깝다면 i->j의 최단거리를 i->k->j로 해줌
					arr[i][j] = arr[i][k] + arr[k][j];
					road[i][j] = road[i][k];
				}
				
			}
		}
	}
}
int main(void) {

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		arr[u][v] = w;
		arr[v][u] = w;

		road[u][v] = v;
		road[v][u] = u;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j && arr[i][j] == 0) arr[i][j] = INF;
		}
	}

	floyd();

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

}