[백준 1504 | C++] 특정한 최단 경로 :: 다익스트라

• 문제 링크 : 1504번: 특정한 최단 경로
• 관련 태그 : 그래프 이론, 최단경로, 데이크스트라
• 참고 자료 : [알고리즘] 다익스트라(Dijkstra) 알고리즘

[알고리즘] 다익스트라(Dijkstra) 알고리즘

 

풀이

단순히 최단 경로를 찾는게 아니라 문제의 제목에서도 알 수 있듯이 '특정한' 최단 경로를 찾는 문제입니다.

문제의 조건은 주어진 두 정점(편의상 a, b 지정)은 반드시 통과해야 한다는 것이다.

문제를 다르게, 단계를 나눠서 바라볼 수 있다.

 

1번 정점부터 N번까지의 정점으로 가는 것이 아닌,

1번 정점부터 a번까지의 정점까지, a번부터 b번 정점까지, b부터 N번 정점까지 가는 경로를 구하는 것이다.

이때 a, b의 순서가 바뀌는 경우를 고려하여 두 경우 중 경로가 더 짧은 것을 고른다.

즉 min(dist(1 → a → b  → N), dist(1 → b → a → N))을 구한다. 

 

#include <iostream>
#include <queue>
#include <vector>
#define INF 987654321

using namespace std;

// end노드까지의 최단 경로의 길이를 반환함
int dijkstra(int start, int end, int n, vector<vector<pair<int, int>>> &graph) {
	
	vector<int>dist(n + 1, INF);
	priority_queue<pair<int, int>>pq;

	dist[start] = 0;	// 시작 노드 거리 0
	pq.push({ 0, start });	// { 거리, 노드 번호}

	while (!pq.empty()) {
		int cur_dist = -pq.top().first;	// 방문하고 있는 정점의 거리
		// 부호 반대인 이유? 우선순위 큐는 최대값을 기준으로 하므로 부호 반대로 넣어준다
		int cur_node = pq.top().second;
		pq.pop();

		for (auto x : graph[cur_node]) {
			int nxt_node = x.first;
			int nxt_dist = cur_dist + x.second;

			if (nxt_dist < dist[nxt_node]) {
				dist[nxt_node] = nxt_dist;
				pq.push({ -nxt_dist, nxt_node });
			}
		}
	}

	if (dist[end] == INF) return -1;	// false
	else return dist[end];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, e;	// 정점의 개수, 간선의 개수
	int a, b;	// 지나가야 하는 두 정점
	cin >> n >> e;

	vector<vector<pair<int, int>>> graph(n + 1);
	for (int i = 0; i < e; i++)
	{
		int from, to, cost;  // 간선의 시작점, 끝점, 가중치
		cin >> from >> to >> cost;
		graph[from].push_back({ to, cost }); 
		graph[to].push_back({ from, cost });
	}
	cin >> a >> b;

	int dist1 = INF;
	int dist2 = INF;
	// 1 -> a -> b -> N
	if (dijkstra(1, a, n, graph) != -1) {
		dist1 = dijkstra(1, a, n, graph);
		if (dijkstra(a, b, n, graph) != -1) {
			dist1 += dijkstra(a, b, n, graph);
			if (dijkstra(b, n, n, graph) != -1) {
				dist1 += dijkstra(b, n, n, graph);
			}
			else { dist1 = INF; }
		}
		else { dist1 = INF; }
	}
	else { dist1 = INF; }


	// 1 -> b -> a -> N
	if (dijkstra(1, b, n, graph) != -1) {
		dist2 = dijkstra(1, b, n, graph);
		if (dijkstra(b, a, n, graph) != -1) {
			dist2 += dijkstra(b, a, n, graph);
			if (dijkstra(a, n, n, graph) != -1) {
				dist2 += dijkstra(a, n, n, graph);
			}
			else { dist2 = INF; }
		}
		else { dist2 = INF; }
	}
	else { dist2 = INF; }

	//cout << dist1 << ' ' << dist2 << endl;

	if (dist1 == INF && dist2 == INF) cout << -1;
	else cout << min(dist1, dist2);
}

• 경로를 없는 경우를 처리하기 힘들었다. 
• dijkstra를 돌리는 동안 한번이라도 경로가 없는 이상 불가능한 경우가 되어버리므로 각 dijkstra마다 조건문을 걸어주었다. 

 

참고하면 좋을 반례

• 글 읽기 - 3%, 10%, 75% 반례입니다
• 글 읽기 - 96% 반례
• 글 읽기 - 계속 75%에서 틀리는데 반례좀 부탁드립니다ㅠㅠ