(백준) 2307번 - 도로검문

문제

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

풀이

그래프에서 특정 간선을 무시할 때, 최단 시간 차이의 최댓값을 구하는 문제이다.

출발 노드가 결정되어 있으므로 먼저 다익스트라를 통해 모든 노드 간 최단 거리를 구한 후, 간선에 대해 순회하며 해당 간선을 무시했을 때 최단 거리를 다익스트라를 통해 구한다.

단, 특정 간선을 무시했을 때 도착 노드에 도달하지 못한다면 -1을 출력하도록 해야 한다.

---

그러나 모든 간선에 대해 무시할 필요는 없다. 기존 최단 거리를 구성하는 간선이 아닌 간선을 무시해봤자 최단 거리를 변하지 않기 때문이다. 처음에 최단 거리를 구할 때 경로를 저장한 후, 해당 간선만 무시하면 이후 다익스트라 실행 횟수를 $M$번에서 $N$번으로 줄일 수 있다.

코드

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

#define INF 2e9

using namespace std;

vector<pair<int, int>> graph[1001]; // {노드, 가중치}
vector<pair<int, int>> edges;
int dist[1001];
int delay[1001];

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

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		graph[a].push_back({ b,c });
		graph[b].push_back({ a,c });

		edges.push_back({ a,b}); // 하나만 저장
	}

	for (int i = 1; i <= n; i++) {
		dist[i] = INF;
		delay[i] = INF;
	}

	// 일단 통제하지 않은 경우 최단 거리를 구한다.
	dist[1] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0,1 });
	while (!pq.empty()) {
		int w = pq.top().first;
		int node = pq.top().second;
		pq.pop();

		if (dist[node] < w) continue;

		for (int i = 0; i < graph[node].size(); i++) {
			int nnode = graph[node][i].first;
			int nw = graph[node][i].second;

			if (w + nw < dist[nnode]) {
				dist[nnode] = w + nw;
				pq.push({ dist[nnode],nnode });
			}
		}
	}

	int maxVal = 0;
	for (int idx = 0; idx < m; idx++) {
		// 통제할 간선
		int x = edges[idx].first;
		int y = edges[idx].second;

		for (int i = 1; i <= n; i++) {
			delay[i] = INF;
		}

		delay[1] = 0;

		pq.push({ 0,1 });
		while (!pq.empty()) {
			int w = pq.top().first;
			int node = pq.top().second;
			pq.pop();

			if (delay[node] < w) continue;

			for (int i = 0; i < graph[node].size(); i++) {
				int nnode = graph[node][i].first;
				int nw = graph[node][i].second;

				if ((node == x && nnode == y) || (node == y && nnode == x)) continue;

				if (w + nw < delay[nnode]) {
					delay[nnode] = w + nw;
					pq.push({ delay[nnode],nnode });
				}
			}
		}

		if (delay[n] == INF) {
			cout << -1;
			return 0;
		}

		maxVal = max(maxVal, delay[n]);
	}

	cout << maxVal - dist[n];
}

시간복잡도

다익스트라 알고리즘의 시간복잡도는 $O(ElogV)$이고, 이를 약 $M$번 반복하므로 전체 시간복잡도는 $(M \cdot MlogN)$이다.

공간복잡도

인접 리스트에서 $O(N+2M)$, 간선 리스트에서 $O(M)$, 최단 거리 배열에서 $O(N)$, 우선순위 큐에서 $O(M)$이므로, 전체 공간복잡도는 $O(N+M$)이다.