백준 5719 거의 최단 경로 C++ 풀이 - 다익스트라, bfs

최단 경로에 쓰인 경로를 절대 사용하지 않고 그 다음 최단 경로를 찾는 문제이다.

아이디어는 아주 간단하다.

1. 최단 경로를 구한다.

2. 백트래킹으로 경로를 제거해준다.

3. 다시 최단 경로를 구한다.

 

아이디어가 간단하고 함정이 없기 때문에 구현에 무게를 두면 된다.

 

fastest 배열에는 cur_node 로 오기전 어떤 node에 있었는지를 기록한다.

 

만약 같은 거리에서 온 node가 있다면 추가만 시켜준다.(그 다음 노트부터는 경로가 동일하므로 queue에 넣지 않는다.)

 

만약 지금 저장된 거리보다 짧은 거리로 왔다면, 지금까지 저장된 경로를 지워주고 새로 저장한다.

 

경로 제거는 dfs (del_fastest(int D) 함수), bfs (del_fastest() 함수) 둘 다 가능하다.

 

해당하는 node를 edge 배열에서 찾아 erase 로 지워준다. 

 

만약 dfs 로 짰다면 메모리 초과 에러에 주의해야하므로 재귀 함수 구조를 잘 생각해서 짜자.

 

시간초과가 난다면 priority_queue를 사용하거나 dfs가 쓸데없는 경우까지 탐색하는 경우가 많으니 주의하자.

 

참고로 다익스트라는 특정 노드에서 갈 수 있는 최단거리를 찾아 업데이트하고, 

업데이트 된 노드에서부터 다시 다른 노드로 갈 수 있는 최단거리를 찾아 업데이트하는 식으로 반복하여

최단경로를 구한다.

 

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;

int N, M, S, D, U, V, P;
vector<pair<int, int>> edge[501];
vector<pair<int,int>> fastest[501];
int dist[501];
priority_queue<pair<int, int>> pq;

int dijkstra(int S, int D) {
	dist[S] = 0;
	int cur_node = S;
	pq.push({ 0, S });
	while (!pq.empty()) {
		cur_node = pq.top().second;
		int cur_cost = -pq.top().first;
		pq.pop();
		if (cur_cost != dist[cur_node]) continue;
		for (int i = 0; i < edge[cur_node].size(); i++) {
			int next_node = edge[cur_node][i].second;
			int next_cost = edge[cur_node][i].first;
			if (dist[next_node] < dist[cur_node] + next_cost) continue;
			//같을 경우 경로 저장해야함
			else if (dist[next_node] == dist[cur_node] + next_cost) {
				fastest[next_node].push_back({ next_cost,cur_node });
			}
			// 더 최단 경로를 발견한 경우 이전 경로 삭제 및 저장
			else {
				fastest[next_node].clear();
				fastest[next_node].push_back({ next_cost,cur_node });
				dist[next_node] = dist[cur_node] + next_cost;
				if (next_node == D) continue;
				pq.push({ -dist[next_node],next_node });
			}
		}
	}
	return 0;
}

void del_fastest(int D) {
	if (D == S) return;
	for (int i = 0; i < fastest[D].size(); i++) {
		int pre_node = fastest[D][i].second;
		int pre_cost = fastest[D][i].first;
		for (int j = 0; j < edge[pre_node].size(); j++) {
			if ( edge[pre_node][j].second==D) {
				del_fastest(pre_node);
				edge[pre_node].erase(edge[pre_node].begin() + j);
				break;
			}
		}
	}
}

void del_fastest() {
	queue<int> q; 
	q.push(D);

	while (!q.empty()) {
		int cur_node = q.front(); q.pop();
		for (int i = 0; i < fastest[cur_node].size(); i++) {
			int prev_node = fastest[cur_node][i].second;
			for (int j = 0; j < edge[prev_node].size(); j++) {
				if (edge[prev_node][j].second == cur_node) {
					edge[prev_node].erase(edge[prev_node].begin() + j);
					q.push(prev_node);
					break;
				}
			}
		}
	}
}

int main() {
	while (1) {
		scanf("%d %d", &N, &M);
		if (N == 0 && M == 0) break;
		//초기화'
		fill_n(dist, sizeof(dist) / sizeof(int), INF);

		for (int i = 0; i <501; i++) {
			fastest[i].clear();
			edge[i].clear();
		}

		scanf("%d %d", &S, &D);
		for (int i = 0; i < M; i++) {
			scanf("%d %d %d", &U, &V, &P);
			edge[U].push_back({ P,V });
		}

		dijkstra(S, D);

		if (dist[D] == INF) {
			printf("-1\n");
			continue;
		}

		//del_fastest();
		del_fastest(D);
		fill_n(dist, sizeof(dist) / sizeof(int), INF);
		dijkstra(S, D);

		if (dist[D] == INF) printf("-1\n");
		else printf("%d\n", dist[D]);
	}
	return 0;
}