[백준1719] 택배 (C++)

📌 문제

BOJ 바로가기

각 집하장에서 최단시간으로 다른 집하장까지 이동할 때 첫 번째로 거쳐야 하는 집하장의 번호를 구해야 한다.

🗡 풀이

📍 플로이드-워셜 알고리즘으로 간단하게 풀 수 있다.

📍 답을 저장할 배열을 선언한 후, 삼중 반복문을 돌릴 때 다음 코드 한 줄을 추가하면 된다.

map[i][j] = map[i][k]

처음에는 map[i][j] = k 이렇게 적었는데, 예제 출력을 확인해보니 오류가 발생하는 것을 확인할 수 있었다.
i -> a -> j 경로에서 i -> a -> b -> j 로 최단경로가 업데이트될 때, map[i][j]의 값이 a에서 b로 바뀌기 때문이었다.
map[i][j] = map[i][k] 와 같이 수정해주면, 최단경로가 업데이트되어도 첫 번째 거쳐가는 집하장의 정보를 유지할 수 있다!

🚩 소스코드

#include <iostream>
using namespace std;
#define INF 987654321;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m, t[201][201], map[201][201];
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) {
				t[i][j] = 0;
				map[i][j] = 0;
			}
			else
				t[i][j] = INF;
		}
	}
	for (int i = 0; i < m; i++) {
		int from, to, time;
		cin >> from >> to >> time;
		t[from][to] = time;
		t[to][from] = time;
		map[from][to] = to;
		map[to][from] = from;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (t[i][j] > t[i][k] + t[k][j]) {
					t[i][j] = t[i][k] + t[k][j];
					map[i][j] = map[i][k]; // ✨ i에서 j로 가는 최단경로가 추가되어도 값이 바뀌지 않음!
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (map[i][j] == 0)
				cout << '-' << ' ';
			else
				cout << map[i][j] << ' ';
		}
		cout << '\n';
	}
}