문제

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

---

풀이

처음에 이 문제를 봤을 때 설계했던 알고리즘은 다음과 같다.

1. 1~N까지 가는 모든 경로를 구한다.
2. 그 중에서 임의의 두 정점 v1, v2를 반드시 경유하는 경로만 고른다.
   • v1 → v2 방향이 불가능 하다면, v1 ← v2 방향으로 돌아서 가면 N번까지 갈 수 있는가?
   • 그것도 불가능 하면, -1 출력한다.
3. 두 정점을 반드시 지나는 경로 중에서 최단 거리를 출력한다.

1번 과정을 구현하기 위해서 DFS로 백트래킹을 수행하려고 했는데,, 코드가 제대로 작동하지 않았다ㅠ 그리고 방법이 비효율적이어서 시간초과가 발생할 거 같다는 불길한 예감도 들었다.

결국 다른 풀이를 참고하니까 다익스트라를 여러 번 적용하는 문제였다!

그리고 가능한 최단 경로는 다음 두 가지 경우밖에 없다.

v1 → v2 → v1 이런 식으로 돌아서 가는 경우에는 최단 경로가 될 수 없기 때문이다.

(i) 1 → ... → v1 → ... → v2 → ... → N
(ii) 1 → ... → v2 → ... → v1 → ... → N

(i) v1 → v2 방향

• 1번에서 v1까지 가는 최단 경로
• v1에서 v2까지 가는 최단 경로
• v2에서 N까지 가는 최단 경로

(i) v2 → v1 방향

• 1번에서 v2로 가는 최단 경로
• v2에서 v1으로 가는 최단 경로
• v1에서 N으로 가는 최단 경로

다익스트라 알고리즘으로 각 단계마다 최단 거리를 구하고, 두 가지 방법 중에 거리의 총합이 더 작은 것이 정답이 된다.

시작 노드를 기준으로 다시 정리해보면 다음과 같다.

• 1번에서 v1 또는 v2로 가는 최단 경로
• v1에서 v2로 가는 최단 경로 (무향 그래프이므로 v2에서 v1으로 가는 최단 경로와 동일)
• v1에서 N으로 가는 최단 경로
• v2에서 N으로 가는 최단 경로

그리고 (i), (ii) 두 가지 방법 모두 불가능 하다면, 1번에서 N번까지 갈 수 있는 경로가 없다는 뜻이므로 -1을 출력한다.

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 805;
const int INF = 1e8;
int N, E, v1, v2;
vector<pii> graph[MAX];
int dist[MAX];

void input(){
	cin >> N >> E; 

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

	cin >> v1 >> v2;
}


void dijkstra(int start) {
	fill(dist, dist + N + 1, INF);
	
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, start});
	dist[start] = 0; 

	while(!pq.empty()){
		auto now = pq.top(); 
		int d = now.first;
		int num = now.second;
		pq.pop(); 

		if(dist[num] < d) continue; 

		for(auto edge: graph[num]){
			int next = edge.first;
			int cost = edge.second;
			int newCost = d + cost;

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

void solution(){
	dijkstra(1);
	int onetov1 = dist[v1];
	int onetov2 = dist[v2];

	dijkstra(v1);
	int v1tov2 = dist[v2];
	int v1toN = dist[N];

	dijkstra(v2);
    int v2toN = dist[N];

	// 간선 가중치의 최대 합은 2억
	int sum1 = onetov1 + v1tov2 + v2toN;
	int sum2 = onetov2 + v1tov2 + v1toN;
	int ans = min(sum1, sum2);
	
	if(ans >= INF){
		cout << "-1\n";
	}else{
		cout << ans;
	}
}

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

	input();
	solution(); 
	
	return 0;
}

이진 트리 기반의 힙 자료구조로 구현되어 있는 우선순위 큐의 삽입/삭제 연산에 대한 시간복잡도는 O(logN)이다.

따라서 다익스트라 알고리즘의 시간복잡도는 O(ElogN) 이라고 할 수 있다.

---

참고 자료

• https://yabmoons.tistory.com/386
• https://hagisilecoding.tistory.com/147