[알고리즘] 백준 1719번: 택배 (C++), 경로 역추적

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

1719번: 택배

이번 문제에서 해결해야 하는 건 "최단 경로를 구했을 때 시작 노드에서 제일 처음 방문한 노드가 어디인가"를 어떻게 찾을지가 포인트였다.

 

(참고 https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-1719-%ED%83%9D%EB%B0%B0)

참고한 포스팅에서 다음과 같이 정리할 수 있었다.

 

1) 다익스트라를 통해 각 노드로부터 최단 경로 구하기

2) 최단 거리를 갱신할 때 backtracking[nextNode] = nowNode;의 형식으로 nextNode에 가는 최단 거리를 가지고 있는 노드는 nowNode임을 알려준다.

(이번 포스팅에서 backtacking은 알고리즘이 아닌 역추적의 의미로 쓰인다.)

 

void dijkstra(int node) {
	priority_queue<pii, vector<pii>, cmp> pq;
	vector<int> dist(n + 1, INF);
	dist[node] = 0;
	pq.push({ node, 0 });

	while (!pq.empty()) {
		int now = pq.top().first;
		int cost = pq.top().second;

		pq.pop();

		if (cost > dist[now]) {
			continue;
		}

		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			int nextCost = graph[now][i].second;
			if (cost + nextCost < dist[next]) {
				dist[next] = cost + nextCost;
				pq.push({ next, dist[next] });

				// 최단 거리 갱신과 동시에 역추적 배열에
				// 최단 거리를 발생시키는 노드(now, next)도 갱신

				// now에서 next로 갔다.
				backtracking[next] = now;
			}
		}
	}
}

 

backtracking[nowNode] = nextNode;가 아닌 backtracking[nextNode] = nowNode;인 이유는 

나중에 코드를 보면 이해할 수 있겠지만

저럴 경우 도착 노드의 직전 노드를 구하게 된다. (그리고 이건 역추적이라기보다는 추적에 가까움)

우리는 출발 노드의 직후 노드를 구하기 때문에 전자의 방법을 써야 한다.

그리고, 다익스트라의 코드 구성을 보면 backTracking[nowNode] = nextNode;라고 하면 구할 수 있는 방법이 보이지 않는다.

 

for (int i = 1; i <= n; i++) {
		// 1) 다익스트라로 i 노드에서 각 노드를 향한 최단 거리 갱신
		dijkstra(i);
		for (int j = 1; j <= n; j++) {
			// 2-1) 시작 노드와 도착 노드가 같으면 '-' 출력
			if (i == j) cout << '-' << ' ';
			// 2-2) 도착 노드가 시작 노드의 직후 노드면 바로 j 출력
			else if (backtracking[i] == j) cout << j << ' ';
			else {
			// 2-3) 도착 노드 j로부터 출발 노드 i까지 역추적
				int node = j;
				while (1) {
					if (i == backtracking[node]) {
						cout << node << ' ';
						break;
					}
					else {
						node = backtracking[node];
					}
				}
			}
		}
		cout << '\n';
	}

 

즉, 이번 문제의 포인트는 "다익스트라에서 사용한 역추적 배열"이다.

 

[AC 코드]

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#define pii pair<int, int>
#define INF 987654321
#define MAX 200 + 1
using namespace std;

vector<pii> graph[MAX];
int backtracking[MAX];

struct cmp {
	bool operator()(pii& a, pii& b) {
		return a.second > b.second;
	}
};

int n, m;

void dijkstra(int node) {
	priority_queue<pii, vector<pii>, cmp> pq;
	vector<int> dist(n + 1, INF);
	dist[node] = 0;
	pq.push({ node, 0 });

	while (!pq.empty()) {
		int now = pq.top().first;
		int cost = pq.top().second;

		pq.pop();

		if (cost > dist[now]) {
			continue;
		}

		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			int nextCost = graph[now][i].second;
			if (cost + nextCost < dist[next]) {
				dist[next] = cost + nextCost;
				pq.push({ next, dist[next] });

				// 최단 거리 갱신과 동시에 역추적 배열에
				// 최단 거리를 발생시키는 노드(now, next)도 갱신

				// now에서 next로 갔다.
				backtracking[next] = now;
			}
		}
	}
}

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

	for (int i = 1; i <= n; i++) {
		// 1) 다익스트라로 i 노드에서 각 노드를 향한 최단 거리 갱신
		dijkstra(i);
		for (int j = 1; j <= n; j++) {
			// 2-1) 시작 노드와 도착 노드가 같으면 '-' 출력
			if (i == j) cout << '-' << ' ';
			// 2-2) 도착 노드가 시작 노드의 직후 노드면 바로 j 출력
			else if (backtracking[i] == j) cout << j << ' ';
			else {
			// 2-3) 도착 노드 j로부터 출발 노드 i까지 역추적
				int node = j;
				while (1) {
					if (i == backtracking[node]) {
						cout << node << ' ';
						break;
					}
					else {
						node = backtracking[node];
					}
				}
			}
		}
		cout << '\n';
	}
	return 0;
}

---

역추적의 공부를 위해 업 솔빙이 필요한 문제

역추적이 되는 것도 최단 경로를 구하는 것이 되는 이유를 확실히 파악 후, 할 수 있는 듯하다.