[백준 1504] 특정한 최단 경로 (C++) - G4

문제

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

1504번: 특정한 최단 경로

 

개요

어제 블로그에 다익스트라(Dijkstra) 알고리즘을 정리한 글을 작성했다.

그리고, 오늘 실제로 다익스트라를 활용한 문제를 풀어보고자 이 문제를 풀어보았다.

예전에는 다익스트라 코드를 무식하게 다 외우기만 해서 시간이 지나면 금방 휘발되었는데, 확실히 알고리즘 동작 과정을 세세하게 이해하면서 코드를 직접 작성하니까 실수 없이 다익스트라 코드를 작성할 수 있었다.

또한, 이 문제는 다익스트라 코드만 알면 조금만 응용해서 금방 풀 수 있는 쉬운 문제였다.

 

문제 풀이

문제에서 "1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다."를 보고 최단 경로 알고리즘을 사용해야 함을 바로 떠올렸다.

또한, 입력으로 주어지는 정점 사이의 거리 c의 범위가 1 ≤ c ≤ 1,000이므로, 음수가 될 수 없기 때문에 다익스트라 알고리즘을 사용해야함을 알 수 있다.

 

다만, 1번 정점에서 시작하여 두 정점 v1, v2를 반드시 거치면서 N번 정점까지 도달해야 한다.

즉, 다음과 같은 2가지 경우가 존재한다.

1) 1 → v1 → v2 → N

2) 1 → v2 → v1 → N 

 

가장 기본적인 다익스트라 문제처럼 dijkstra(1)만 작성하면 1번 정점으로부터 각 정점까지의 최소 거리밖에 알 수 없다.

첫번째 경우만 보더라도, 우리는 1번 정점에서 v1 정점까지의 최소 거리뿐만 아니라, v1 정점으로부터 v2 정점까지의 최소 거리도 알아야 하고, v2 정점에서 N번 정점까지의 최소 거리도 알아야 한다.

 

즉, 다익스트라를 한 번만 실행해서는 안 되고, 시작점을 v1, v2로 하는 다익스트라를 추가적으로 실행해주어야 한다.

 

dijkstra(1)을 통해 1 → v1, 1 → v2 최소 거리를 알 수 있다.

dijkstra(v1)을 통해 v1 → v2, v1  → N 최소 거리를 알 수 있다.

(방향 없는 그래프이므로 v1 → v2 최소 거리와 v2 → v1 최소 거리는 같다.)

dijkstra(v2)을 통해 v2 → N 최소 거리를 알 수 있다.

즉, 3번의 다익스트라를 실행하면 된다.

주의할 점은 다음 다익스트라 실행 전에 fill 함수를 통해 dist 배열의 모든 값을 다시 INF로 초기화해주어야 한다.

 

코드

#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>

#define INF (~0U >> 2) // 약 10억 7천만 (1073741823)

using namespace std;
using pii = pair<int, int>;

vector<pii> adj[801];
vector<int> dist(801, INF);

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

	while (!pq.empty()) {

		int cur_dist = pq.top().first; // 현재 정점까지의 최소 거리
		int cur = pq.top().second;
		pq.pop();

		if (dist[cur] < cur_dist) continue;

		for (auto k : adj[cur]) {

			int next_dist = k.first; // 현재 정점에서 다음 정점까지의 거리
			int next = k.second;

			if (cur_dist + next_dist < dist[next]) {
				dist[next] = cur_dist + next_dist;
				pq.push({ dist[next], next });
			}

		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	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;
		adj[a].push_back({ c, b });
		adj[b].push_back({ c, a });
	}
	int v1, v2; cin >> v1 >> v2;
	
	// 1 -> v1 -> v2 -> n
	// 1 -> v2 -> v1 -> n

	dijkstra(1);
	int s_to_v1 = dist[v1]; // 1 -> v1
	int s_to_v2 = dist[v2]; // 1 -> v2
	fill(dist.begin(), dist.end(), INF);

	dijkstra(v1);
	int v1_to_v2 = dist[v2]; // v1 -> v2 <=> v2 -> v1
	int v1_to_n = dist[n]; // v1 -> n
	fill(dist.begin(), dist.end(), INF);

	dijkstra(v2);
	int v2_to_n = dist[n];

	int sum1 = s_to_v1 + v1_to_v2 + v2_to_n;
	int sum2 = s_to_v2 + v1_to_v2 + v1_to_n;
	int ans = min(sum1, sum2);
	
	if (ans >= INF) cout << -1;
	else cout << ans;
	
	return 0;
}

 

깨달은 점

다익스트라 알고리즘을 이용한 문제를 풀어보았는데, 난이도는 Gold IV이지만, 코드를 확실히 이해하고 나니까 그렇게 어렵게 느껴지지 않았다.

빠른 시일 내에 벨만-포드 알고리즘과 플로이드-와샬 알고리즘도 블로그에 글을 작성하며 공부해야겠다.