[알고리즘] 백준 5719번: 특정한 최단 경로 (C++), 경로 역추적(2)

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

5719번: 거의 최단 경로

답을 구하는 순서는 쉽게 알아낼 수 있었다.

1) 다익스트라를 통해 최단 경로 탐색

2) 해당 최단 경로를 없앰

3) 다시 한번 다익스트라를 통해 최단 경로를 구함

 

'해당 최단 경로를 없앰'을 해결하는 게 이번 문제의 핵심이다.

 

솔루션을 참고(https://jaimemin.tistory.com/617)하기도 했고, 바로 전에 풀었던 문제에서 '경로 역추적'이라는 키워드를 건드려 봤기 때문에 이해는 쉽게 되었었다.

 

배열(trace) 선언을 통해 다익스트라를 돌리면 최단 경로를 담게 만들어야 한다.

다익스트라 중 일부분을 가져와봤다.

if (cost + nextCost < dist[next]) {
	dist[next] = cost + nextCost;
	pq.push(make_pair(next, dist[next]));
				
	// 최단 경로를 발생시키는 경로들 갱신
	trace[next].clear(); // 더 작은 경로를 만나면 초기화
	trace[next].push_back(make_pair(now, dist[next]));
}
else if (cost + nextCost == dist[next]) {
	trace[next].push_back(make_pair(now, dist[next]));
}

역시 이 솔루션 또한 '경로 역추적'과 유사하며 다익스트라를 꿰뚫고 있어야 이해가 가능하다.

 

2번째 방법의 '해당 최단 경로 없앰'은 다익스트라를 끝낸 후, BFS를 통해 처리해야 한다.

void bfs(int end, vector<pair<int, int>> trace[MAX]) {
	queue<int> q;
	q.push(end);
	while (!q.empty()) {
		int front = q.front();
		q.pop();

		for (int i = 0; i < trace[front].size(); i++) {
			int next = trace[front][i].first;

			if (!visited[front][next]) {
				visited[front][next] = 1;
				for (int j = 0; j < graph[next].size(); j++) {
					// next가 행 자리에 있는 이유는 역으로 담았기 때문에
					// 그래프 입장에서 가는 길을 없애야 한다.
					if (graph[next][j].first == front) {
						graph[next][j].second = -1;
					}
				}

				q.push(next);
			}
		}
	}
}

 

[AC 코드]

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <cstring>
#define MAX 500
#define INF 987654321
using namespace std;

vector<pair<int, int>> graph[MAX];
bool visited[MAX][MAX];

struct cmp {
	bool operator()(pair<int, int>& a, pair<int, int>& b) {
		return a.second > b.second;
	}
};

vector<int> dijkstra(vector<pair<int, int>> trace[MAX], int node, int n) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
	vector<int> dist(n, INF);
	dist[node] = 0;
	pq.push(make_pair(node, 0));
	while (!pq.empty()) {
		int now = pq.top().first;
		int cost = pq.top().second;

		pq.pop();

		if (dist[now] < cost) {
			continue;
		}

		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			int nextCost = graph[now][i].second;

			if (graph[now][i].second == -1) {
				continue;
			}

			if (cost + nextCost < dist[next]) {
				dist[next] = cost + nextCost;
				pq.push(make_pair(next, dist[next]));
				
				// 최단 경로를 발생시키는 경로들 갱신
				trace[next].clear(); // 더 작은 경로를 만나면 초기화
				trace[next].push_back(make_pair(now, dist[next]));
			}
			else if (cost + nextCost == dist[next]) {
				trace[next].push_back(make_pair(now, dist[next]));
			}
		}
	}
	return dist;
}

void bfs(int end, vector<pair<int, int>> trace[MAX]) {
	queue<int> q;
	q.push(end);
	while (!q.empty()) {
		int front = q.front();
		q.pop();

		for (int i = 0; i < trace[front].size(); i++) {
			int next = trace[front][i].first;

			if (!visited[front][next]) {
				visited[front][next] = 1;
				for (int j = 0; j < graph[next].size(); j++) {
					// next가 행 자리에 있는 이유는 역으로 담았기 때문에
					// 그래프 입장에서 가는 길을 없애야 한다.
					if (graph[next][j].first == front) {
						graph[next][j].second = -1;
					}
				}

				q.push(next);
			}
		}
	}
}

int main() {
	int n, m;
	for (;;) {
		cin >> n >> m;
		if (n == 0 && m == 0) {
			break;
		}

		for (int i = 0; i < MAX; i++) {
			graph[i].clear();
		}
		memset(visited, false, sizeof(visited));
		vector<pair<int, int>> trace[MAX];

		int s, d;
		cin >> s >> d;

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

		dijkstra(trace, s, n);

		bfs(d, trace);

		vector<int> result = dijkstra(trace, s, n);
		if (result[d] == INF) {
			cout << -1 << '\n';
		}
		else {
			cout << result[d] << '\n';
		}
	}
	return 0;
}

---

다익스트라 + BFS만으로도 업 솔빙 할 이유는 충분하다. 다만, 경로 역추적이라는 키워드를 구현해야 풀리는 이유까지 덧대어 업 솔빙은 필수다.