백준 2307 - 도로검문(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2307

2307번: 도로검문

다익스트라를 사용해 푸는 문제입니다.

도로를 하나 제한했을 때, 지연시킬 수 있는 최대 시간을 구하는 문제입니다.

모든 길을 제한한다고 한다면, 도로의 수가 5,000개이기에 다익스트라를 5000개를 확인을 해야합니다.

따라서, 다른 방법을 이용해야 하는데, 생각을 해본다면, 최단 거리일 떄의 길을 제외하고 제한한다면, 값은 항상 최단 거리의 값이 될 것입니다.
문제에서 주어진 그림으로 확인해 본다면, (1 -> 4), (4 -> 5), (5 -> 6), (3, -> 4)의 길을 제한한다고 해도,
항상 최단 거리를 갈 수 있기에 값은 4가 고정으로 나올 것입니다.

그러므로, 최단 거리의 길을 저장해둔 뒤, 해당하는 도로를 하나씩 제한하면서 값을 구하는 방식으로 하면 된다는 것을 확인할 수 있습니다.

먼저, 길을 제한하기 전 최단 거리의 값과 최단 거리의 도로를 저장해주면 됩니다.
도로를 저장하는 방법은 해당 정점의 부모를 저장하면 되는데, 최단거리를 갱신하는 과정에서 바꿔주면 됩니다.
그림으로 확인하면 (6 -> 3), (3 - > 2), (2 -> 1)로 저장해주면 됩니다.

2가지 값을 구했다면, 도로를 하나씩 제한하면서 최단 경로를 찾아준 뒤, 증가한 시간을 구해주면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF INT_MAX
#define F first
#define S second

using namespace std;

int N, M;
vector<pair<int, int>> connect[1001];
int Distance[1001], parent[1001]; //최단 거리를 기록, 자신의 부모를 기록
priority_queue<pair<int, int>> q;
bool Erase = true; // true일 경우->경로를 제한하기 전, false->경로를 제한

void reset_distance(){ //최단 거리를 전부 초기화
	for(int i = 1; i <= N; i++) Distance[i] = INF;
}

void Dijstra(int node1, int node2){
	q.push({-0, 1});
	Distance[1] = 0;
	while(!q.empty()){
		int x= q.top().S;
		int cost = -q.top().F;
		q.pop();
		if(Distance[x] > cost) continue;
		for(int i = 0 ; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			int n_cost = cost + connect[x][i].S;
			//현재 가려는 곳이 제한된 길일 때
			if((node1 == x && node2 == xx) || (node1 == xx && node2 == x)) continue;
			if(Distance[xx] > n_cost){
				//최단 거리를 구할 때, 자신의 부모를 저장한다.
				if(Erase) parent[xx] = x;
				Distance[xx] = n_cost;
				q.push({-Distance[xx], xx});
			}
		}
	}	
}

void solve(){
	int min_time = INF, increase_time = -INF;
	parent[1] = 1;
	reset_distance();	
	if(Erase) Dijstra(0, 0);
	Erase = false;
	min_time = Distance[N];
	//최단 거리의 길을 하나씩 제한해 가면서 찾아보면 된다.
	for(int i = N; parent[i] != i; i = parent[i]){
		reset_distance();
		Dijstra(i, parent[i]);
		if(Distance[N] == INF){
			increase_time = -1;
			break;
		}
		else{
			increase_time= max(increase_time, Distance[N] - min_time);
		}
	}
	cout << increase_time;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		scanf("%d %d %d", &x, &y, &cost);
		connect[x].push_back({y, cost});
		connect[y].push_back({x, cost});
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.