백준 1719번 | 택배 (C++ 풀이)

 

 

 

  문제  

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

1719번: 택배

---

  풀이  

• 사용 알고리즘 : 다익스트라
• 시간 복잡도 : $O(N*MlogN + N^3)$

정점 $V_{1}$ 에서 정점 $V_{2}$ 로 향하는 최단 경로 중, 정점 $V_{1}$ 에서 바로 다음 정점이 어디인지 찾아야 하는 문제입니다.

 

문제를 풀기 위한 메인 아이디어는 최단 경로 역추적입니다. 최단 거리가 계산되는 시점에서 지나쳤던 정점들을 역추적한 뒤, 실제 최단 경로를 구성하고 두 번째로 방문했던 정점을 찾아주면 됩니다.

 

이 문제는 모든 경우에 대한 최단 경로를 구할 필요가 있어서 플로이드-와샬을 사용하는게 편하지만, 이 글에서는 다익스트라를 활용한 풀이를 소개해보겠습니다.

 

다익스트라로 실제 최단 경로를 추적하기 위해선, 최단 경로 배열 $dist$ 의 값이 새로 갱신되는 순간에 방문중인 정점을 기록해주면 됩니다.

이해가 어려울 수 있으니 그림으로 한 번 설명해보겠습니다.

 

$A$ → $C$ 로 가는 최단 경로를 구해볼 건데, $A$ 에서 출발할 것이기 때문에 $dist[A] = 0$ 으로 먼저 초기화를 시켜주었습니다.

또한, $prev$ 라는 역추적 배열을 하나 만들어주었는데, $prev[V_{1}] = V_{2}$ 는 $V_{1}$ 이전에 방문해야 하는 정점이 $V_{2}$ 라는 뜻을 의미합니다.

$prev[A]$ 같은 경우는 의미 없는 값이기 때문에 그냥 $A$ 를 넣어주었습니다.

 

그렇다면 이제 $A$ 에 인접한 정점 중 $B$ 를 먼저 방문한다고 해보겠습니다.

$A$ 에서 $B$ 를 방문하는 시점에 $dist[B]$ 의 값이 갱신됐습니다. 이 말은 무슨 뜻일까요?

바로 $A$ 에서 $B$ 로 갈때가 최단 경로가 된다는 의미이겠죠. 따라서 $prev[B] = A$ 가 됩니다.

 

이번에는 $A$ 에서 $C$ 를 방문합니다. 이 시점에 $dist[C]$ 의 값이 갱신되었고, 이는 $A$ 에서 $C$ 를 방문할 때가 현재까지의 최단 경로임을 의미합니다.

따라서 이 역시 $prev[C] = A$ 가 되겠죠.

 

이제 $A$ 는 방문을 마쳤으니 $dist[A]$ 의 값은 확정이 됐습니다. 아직 방문되지 않은 정점 중 가장 작은 $dist$ 값을 가진 $B$ 를 방문해볼텐데요.

$B$ 에서 $A$ 로 가는 경로는 이미 최적이 아니기 때문에 생략하도록 하겠습니다.

 

그렇다면 $B$ 에서 $C$ 를 방문해보겠습니다. 이때 $dist[C] = dist[B] + 3 = 4$ 가 되어 $dist[C]$ 의 값이 새롭게 갱신됩니다.

즉, $B$ 에서 $C$ 를 방문하는 경우가 새로운 최단 경로가 된다는 의미겠죠. 따라서 $prev[C] = B$ 로 다시 갱신됩니다.

 

자, 이제 다익스트라를 통한 최단 경로 계산은 모두 끝났습니다.

그렇다면 이제 $prev$ 배열에 기록해둔 정점들을 역으로 따라가며 최단 경로를 구성해주기만 하면 됩니다.

최종 완성된 $prev$ 배열을 통해 역으로 경로를 찾아나가면 이런 느낌으로 찾을 수 있을 겁니다.

결과적으로 $C$ → $B$ → $A$ 라는 경로가 만들어질 것이고, 이를 뒤집은 $A$ → $B$ → $C$ 경로가 $A$ → $C$ 로 향하는 최단 경로가 되겠죠.

 

이를 모두 정리해보자면 위 그림처럼 될 겁니다.

 

 

지금까지 다익스트라로 실제 최단 경로를 어떻게 찾아내는지 알아봤습니다.

다익스트라를 돌리면서 $dist$ 값이 새롭게 갱신되는 시점에, $prev$ 배열에 바로 이전 정점을 기록해두고 이를 역추적하여 실제 최단 경로를 찾아내는 방법입니다.

 

이제 최단 경로는 구했으니, 두 번째로 방문한 정점만 찾아주면 쉽게 문제를 풀어낼 수 있습니다.

---

  코드  

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const int inf = 2e9;
const int SIZE = 1 << 18;
const int MOD = 1e9 + 7;

vector<pii> adj[1001];
int dist[1001];
int prevv[1001];

void dijkstra(int start) {
	for (int i = 0; i < 1001; i++) dist[i] = inf;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	dist[start] = 0;
	pq.push({0, start});
	while (!pq.empty()) {
		int cur_dist = pq.top().X;
		int cur_node = pq.top().Y;
		pq.pop();
		if (dist[cur_node] < cur_dist) continue;
		for (pii next : adj[cur_node]) {
			int next_node = next.X;
			int next_dist = dist[cur_node] + next.Y;
			if (next_dist >= dist[next_node]) continue;
			dist[next_node] = next_dist;
			prevv[next_node] = cur_node;
			pq.push({next_dist, next_node});
		}
	}
}

int findAns(int start, int end) {
	while (1) {
		if (prevv[end] == start) return end;
		end = prevv[end];
	}
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m;
	cin >> n >> m;
	vector<int> num;
	for (int i = 0; i < m; i++) {
		int u, v, cost;
		cin >> u >> v >> cost;
		num.push_back(u);
		num.push_back(v);
		adj[u].push_back({v, cost});
		adj[v].push_back({u, cost});
	}
	sort(num.begin(), num.end());
	num.erase(unique(num.begin(), num.end()), num.end());
	for (int i = 0; i < n; i++) {
		string s = "";
		dijkstra(num[i]);
		for (int j = 0; j < n; j++) {
			if (i == j) {
				s += "- ";
				continue;
			}
			s += to_string(findAns(num[i], num[j])) + " ";
		}
		cout << s << '\n';
	}
	return 0;
}