[알고리즘] 백준 1504번: 특정한 최단 경로 (C++)

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

1504번: 특정한 최단 경로

이 문제는 다익스트라를 활용한 응용력을 필요로 했다.

 

주어진 v1, v2를 거치는 경로를 어떻게 필수적으로 보낼지 생각해야 한다.

(참고 https://jaimemin.tistory.com/1004)

우선순위 큐에 3개의 원소(노드, 비용, v1 or v2를 지났는가의 여부)를 고민했지만 이는 더 심오한 코드가 만들어졌었다.

그래서 참고를 했다.

 

이 솔루션에서는 다음과 같은 키워드를 얻어낼 수 있었다.

1. 1 -> v1 -> v2 -> N or 1 -> v2 -> v1 -> N
2. 다익스트라 알고리즘의 리턴형이 vector 배열

---

1) 1 -> v1 -> v2 -> N or 1 -> v2 -> v1 -> N

 

거쳐서 갈 수 있는 방법이 2가지라는 뜻이다.

즉, 저 두 경로는 다익스트라를 통해 다음과 같이 나타낼 수 있다.

이번 문제의 포인트가 되는 부분이다. 다익스트라의 응용력

vector<int> from1 = dijkstra(1);
vector<int> fromv1 = dijkstra(v1);
vector<int> fromv2 = dijkstra(v2);

int path1 = from1[v1] + fromv1[v2] + fromv2[N];
int path2 = from1[v2] + fromv2[v1] + fromv1[N];
	
int answer = min(path1, path2);
if (answer >= INF || answer < 0) {
	cout << -1;
}
else {
	cout << answer;
}

 

[+ answer가 0 미만이라는 조건이 달린 이유]

오버플로우 때문이다. INF를 987654321로 잡아줬기 때문에 세 경로 모두 INF가 나버리면 int의 범위를 넘어버린다.

int범위를 넘어버릴 경우 int의 범위에서 제일 아래로 내려가 연산을 계속해나간다.

오버플로우를 일부러 구현해보았다.

#include <iostream>
#include <climits>
using namespace std;

int main() {
	int a = INT_MAX;
	a += 1;
	cout << a;
	return 0;
}

output
-2147483648

---

2) 다익스트라 알고리즘의 리턴형이 vector 배열

1번 키워드를 알고 나서 그럼 dist[](비용을 담는 배열)은 매번 초기화시켜줘야 하는 번거로움이 생기겠다 싶었지만

다익스트라 알고리즘의 리턴 자체를 vector로 리턴하고, 다익스트라 안에서 dist 배열을 선언했다는 점이 이번 문제에서 챙겨야 할 포인트 두 번째였다.

vector<int> dijkstra(int node) {
	// 거리 INF로 초기화
	vector<int> dist(N + 1, INF);
    dist[node] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	pq.push(make_pair(node, 0));
	while (!pq.empty()) {
		int now = pq.top().first;
		int cost = pq.top().second;

		pq.pop();
		if (dist[now] < cost) {
			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(make_pair(next, dist[next]));
				trace[next] = now;
			}
		}
	}

	return dist;
}

---

[AC 코드]

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

vector<pair<int, int>> graph[MAX];
int trace[MAX];
int N, E;

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

vector<int> dijkstra(int node) {
	// 거리 INF로 초기화
	vector<int> dist(N + 1, INF);
    dist[node] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	pq.push(make_pair(node, 0));
	while (!pq.empty()) {
		int now = pq.top().first;
		int cost = pq.top().second;

		pq.pop();
		if (dist[now] < cost) {
			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(make_pair(next, dist[next]));
				trace[next] = now;
			}
		}
	}

	return dist;
}

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

	int v1, v2;
	cin >> v1 >> v2;

	vector<int> from1 = dijkstra(1);
	vector<int> fromv1 = dijkstra(v1);
	vector<int> fromv2 = dijkstra(v2);

	int path1 = from1[v1] + fromv1[v2] + fromv2[N];
	int path2 = from1[v2] + fromv2[v1] + fromv1[N];
	
	int answer = min(path1, path2);
	if (answer >= INF || answer < 0) {
		cout << -1;
	}
	else {
		cout << answer;
	}

	return 0;
}

---

다익스트라를 시작할 때 자신으로 가는 비용을 0으로 초기화시켜주지 않아서 계속 오류가 났었다.

이번 문제는 다익스트라를 응용한 문제로 다익스트라의 부수적인 테크닉을 배울 수 있는 계기가 되었다.