[BOJ 5719] 거의 최단 경로

문제

BOJ 5719 거의 최단 경로

유형

• 다익스트라 알고리즘

풀이

기본 다익스트라 알고리즘을 이용한 최단 경로 문제에서 최단 경로를 저장하여 제거하는 작업이 한번 필요한 문제였다.

최단 경로를 저장하기 위해서 하나의 배열을 설정하여 최단 거리가 갱신될 때마다 각 노드를 저장하면 된다.

메모리 초과나 시간 초과가 많이 발생하였는데 원본 문제에 비해서 메모리 제한이 낮고 BOJ에는 비효율적인 코드를 잡아내는 테케가 존재하는 것 같다.

메모리 초과가 발생했던 경우는 최단 경로를 삭제하기 위해 bfs를 사용하거나 삭제된 경로를 저장하기 위해 새로운 N*N개의 배열을 만들었을 경우 혹은 다익스트라에서 최단 거리가 같을 때에도 큐에 삽입하는 경우이다.

이를 해결하기 위해 경로 삭제는 dfs를 사용하였고 경로 삭제를 저장하기 위해 기존 경로의 길이를 -1로 조정하였다.

시간 초과가 발생하는 경우는 경로 삭제 부분에서 방문한 노드를 체크해주지 않으면 발생하게 된다.

결론적으로 풀이는
1. 다익스트라 알고리즘으로 최단 경로 및 거리 구하기
2. 최단 경로 삭제
3. 한번더 다익스트라 알고리즘으로 최단 거리 찾기

코드

// 5719
#include <bits/stdc++.h>
using namespace std;

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

int n, m, S, D;
vector<int> pre[500];
vector<int> dist(500);
map<int, int>adj[500];
vector <bool> visited(500);

void deletePath(int now) {
	if (now == S) return;

	if (visited[now]) return;
	visited[now] = true;
	
	for (int i = 0; i < pre[now].size(); i++) {
		int next = pre[now][i];
		adj[next][now] = -1;
		deletePath(pre[now][i]);
	}
}

void shortestPath() {
	for (int i = 0; i < n; i++) dist[i] = INT32_MAX;
	priority_queue<pair<int, int>> pq;
	pq.emplace(0, S);
	dist[S] = 0;
	while (!pq.empty()) {
		int now = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();

		if (cost > dist[now]) continue;

		for (auto x : adj[now]) {
			int next = x.first;
			int ncost = x.second;
			if (ncost == -1) continue;

			if (dist[next] > dist[now] + ncost) {
				pre[next].clear();
				pre[next].emplace_back(now);
				dist[next] = dist[now] + ncost;
				pq.emplace(-dist[next], next);
			}
			else if (dist[next] == dist[now] + ncost) pre[next].emplace_back(now);
		}
	}
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);

	while (true) {
		cin >> n >> m;
		if (n == 0 && m == 0) break;
		cin >> S >> D;

		for (int i = 0; i < n; i++) {
			adj[i].clear();
			pre[i].clear();
			visited[i] = false;
		}

		for (int i = 0; i < m; i++) {
			int u, v, p;
			cin >> u >> v >> p;
			adj[u][v] = p;
		}

		shortestPath();
		deletePath(D);
		shortestPath();

		if (dist[D] == INT32_MAX) cout << -1 << '\n';
		else cout << dist[D] << '\n';
	}


	return 0;
}