[알고리즘] 백준 5719 거의 최단 경로

📖문제

5719 거의 최단 경로

💡구상

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다.

우선 최단경로를 찾고 그 최단경로에 해당하는 간선들을 끊은 후 다시 최단경로를 찾는 방식으로 생각해봤다.

처음에는 최단경로를 찾을 때 플로이드 워셜을 사용했다.
그 결과는...

그래서 시간복잡도가 더 낮은 다익스트라를 사용해서 문제를 해결했다.

🔍코드

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int INF = 987654321;
int n,m,s,d,u,v,p,ret=INF;
int edge[503][503];
int dist[503];
priority_queue<int,vector<int>,greater<int>> pq;

void dijkstra(){
	fill(dist,dist+504,INF);
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	pq.push({0,s});
	dist[s]=0;
	while(pq.size()){
		int here = pq.top().second;
		int here_dist = pq.top().first;
		pq.pop();
		for(int i=0; i<n; i++){
			if(edge[here][i] == -1) continue;
			int _dist = edge[here][i];
			if(dist[i] > dist[here] + _dist){
				dist[i] = dist[here] + _dist;
				pq.push({dist[i],i});
			}
		}
	}
}
void erase_edge(){
	queue<int> q;
	q.push(d);
	while(q.size()){
		int dis = q.front();
		q.pop();
		for(int i=0; i<n; i++){
			if(dist[dis] == dist[i] + edge[i][dis] && edge[i][dis] != -1){
				edge[i][dis] = -1;
				q.push(i);
			}
			
		}
	}
}
int main() {
	while(true){
		cin>>n>>m;
		if(n==0 && m==0) break;
		cin>>s>>d;
		memset(edge,-1, sizeof(edge));
		while(m--){
			cin>>u>>v>>p;
			edge[u][v]=p;
		}
		dijkstra();
		erase_edge();
		dijkstra();
		ret = dist[d];
		if(ret==INF) cout<<"-1\n";
		else cout<<ret<<"\n"; 
	}
	return 0;
}

다익스트라

void dijkstra(){
	fill(dist,dist+504,INF);
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
	pq.push({0,s});
	dist[s]=0;
	while(pq.size()){
		int here = pq.top().second;
		int here_dist = pq.top().first;
		pq.pop();
		for(int i=0; i<n; i++){
			if(edge[here][i] == -1) continue;
			int _dist = edge[here][i];
			if(dist[i] > dist[here] + _dist){
				dist[i] = dist[here] + _dist;
				pq.push({dist[i],i});
			}
		}
	}
}

시작점인 s로부터 모든 정점까지의 거리에 대한 최솟값을 갱신한다.

간선 지우기

void erase_edge(){
	queue<int> q;
	q.push(d);
	while(q.size()){
		int dis = q.front();
		q.pop();
		for(int i=0; i<n; i++){
			if(dist[dis] == dist[i] + edge[i][dis] && edge[i][dis] != -1){
				edge[i][dis] = -1;
				q.push(i);
			}
			
		}
	}
}

목적지인 e로부터 시작하면서 최단거리인지 확인한 후, 최단거리라면 간선을 지우는 식으로 진행한다.

🔥배운 점

플로이드 워셜 vs 다익스트라

플로이드 워셜은 모든 정점에 대한 최소쌍을 찾을 수 있지만 시간복잡도가 O(n^3) 이다.
다익스트라는 한 정점으로 부터의 모든 정점까지의 최단거리를 구할 수 있지만 시간복잡도가 O(n^3) 이다.

이번 문제는 한 정점으로 부터 시작해 목적지 정점으로 까지 가는 경우만 구하면 되므로 다익스트라를 사용해야 했다. 알고리즘의 시간복잡도와 특징을 잘 파악해서 사용하자!