[백준/C++] 1504번 : 특정한 최단 경로 (다익스트라 연습)

특정한 최단 경로

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제 입력 1

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1

7

---

해당 문제는 1번 정점부터 N번 정점까지 최단 거리로 이동할 때, 두 개의 정점(v1, v2)를 무조건 지나는 경우의 최단 경로를 구해야한다.

 

음수의 가중치가 없고, 한 정점에서 모든 정점까지의 최단경로를 비교하며 구해야하기 때문에 다익스트라 알고리즘을 사용하여 풀이했다.

 

반드시 통과해야하는 두 정점을 v1 과 v2 라고 하면, 나타날 수 있는 경로는 두가지이다.

Start → V1 → V2 → End
Start → V2 → V1 → End

 

따라서 위와 같은 경로를 모두 구해서 비교하기 위해 다익스트라 알고리즘을 3번에 나누어 수행하였다.

 

1. Start 부터 v1까지의 거리 & Start 부터 v2까지의 거리

2. v1부터 v2까지의 거리 == v2부터 v1까지의 거리 (무방향 그래프이므로 같다)

3. v2부터 End 까지의 거리 (v1부터 End까지의 거리는 2번에서 한번에 구할 수 있다)

 

이러한 흐름으로 풀이한 코드는 아래와 같다.

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;

#define INF 987654321

vector<pair<int, int>> graph[801];
vector<int> dist(801);

void Dijkstra(int start)
{
	fill(dist.begin(), dist.end(), INF);

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
	pq.push({ 0, start });
	dist[start] = 0;

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

		for (int i = 0; i < graph[cur].size(); i++)
		{
			int next = graph[cur][i].first;
			int nCost = graph[cur][i].second;

			if (dist[next] > cost + nCost)
			{
				dist[next] = cost + nCost;
				pq.push({ dist[next], next });
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

	int s_v1, s_v2, v1_v2, v1_e, v2_e;

	// 1번째 case : Start -> v1, Start -> v2
	Dijkstra(1);
	s_v1 = dist[v1];
	s_v2 = dist[v2];

	//2번째 case : v1 -> v2 (= v2 -> v1)
	Dijkstra(v1);
	v1_v2 = dist[v2];
	v1_e = dist[N];

	// 3번째 case : v2 -> End
	Dijkstra(v2);
	v2_e = dist[N];

	// 최종 연산
	int result = INF;
	result = min(result, s_v1 + v1_v2 + v2_e);
	result = min(result, s_v2 + v1_v2 + v1_e);

	if (result == INF || v1_v2 == INF)
		result = -1;

	cout << result;

	return 0;
}

 

다익스트라 알고리즘을 구현하여 Dijkstra 함수로 작성해두고, 위에서 말한 세가지 케이스로 나누어 다익스트라를 수행하였다.

 

이때, 각 과정에서 도출되는 거리 값을 s_v1, s_v2, ... , v1_e, v2_e 변수에 저장하였고

최종 연산에서는 result 값을 무한대로 초기화한 뒤, 두가지 경로 중 더 작은 경로의 값을 갖는걸로 초기화해주었다.

 

다익스트라 알고리즘을 구현할 줄 알면 어렵지 않은 문제인데, 꼭 방문해야 하는 노드가 있는 경우 다익스트라 알고리즘을 나눠서 수행하는 아이디어가 쉽게 떠오르지 않은 것 같다.

---

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

1504번: 특정한 최단 경로