거의최단경로
문제 해석
거의 최단경로를 찾는 문제입니다.
여기서 거의 최단경로란 최단경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 경로를 말합니다.
설계(20)
최단경로를 찾아서 해당 경로를 없애고 다시한번 최단경로를 구하면 되는 문제입니다.
저는 다음의 과정을 거치도록 설계하였습니다.
- 다익스트라알고리즘으로 최단경로를 갱신합니다. 이와 동시에 경로를 찾을 수 있도록 이전경로를 저장해놓습니다.
- 도착지점에서 시작해서 저장된 경로로 역추적하여서 최단경로를 체크합니다.
- 다시한번 다익스트라 알고리즘을 사용하여 최단경로를 찾는데, 최단경로로 사용된 엣지를 제외하고 갱신합니다.
구현(40)
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define MAXN 501
bool min_arr[MAXN][MAXN];
vector<pair<int,int> > adj[MAXN];
int dist[MAXN];
bool visited[MAXN];
vector<int> path[MAXN];
priority_queue<pair<int, int> > pq;
queue<int> q;
int N, M,S,D;
void dijkstra() {
memset(dist, -1, sizeof(dist));
pq.push({ 0,S });
dist[S] = 0;
while (!pq.empty()) {
int cur_dist = -pq.top().first;
int cur = pq.top().second;
pq.pop();
if (cur_dist != dist[cur]) continue;
for (int i = 0; i < adj[cur].size(); i++) {
int next = adj[cur][i].first;
int next_dist = adj[cur][i].second + cur_dist;
if (dist[next] == -1 || dist[next] >= next_dist) {
if (dist[next] == -1 || dist[next] > next_dist) {
path[next].clear();
path[next].push_back(cur);
dist[next] = next_dist;
pq.push({ -next_dist,next });
}
else if (dist[next] == -1 || dist[next] == next_dist) {
path[next].push_back(cur);
}
}
}
}
}
void bfs() {
memset(visited, false, sizeof(visited));
q.push(D);
visited[D] = true;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = 0; i < path[cur].size(); i++) {
int next = path[cur][i];
min_arr[next][cur] = true;
if (visited[next]) continue;
visited[next] = true;
q.push(next);
}
}
}
int dijkstra1() {
memset(dist, -1, sizeof(dist));
pq.push({ 0,S });
dist[S] = 0;
while (!pq.empty()) {
int cur_dist = -pq.top().first;
int cur = pq.top().second;
pq.pop();
if (cur_dist != dist[cur]) continue;
for (int i = 0; i < adj[cur].size(); i++) {
int next = adj[cur][i].first;
int next_dist = adj[cur][i].second + cur_dist;
if (min_arr[cur][next]) continue;
if (dist[next] == -1 || dist[next] > next_dist) {
dist[next] = next_dist;
pq.push({ -next_dist,next });
}
}
}
return dist[D];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
while (1) {
memset(min_arr, false, sizeof(min_arr));
for (int i = 0; i < MAXN; i++) {
path[i].clear();
adj[i].clear();
}
cin >> N >> M;
if (N == 0 && M == 0) break;
cin >> S >> D;
while (M--) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({ v,w });
}
dijkstra();
bfs();
cout << dijkstra1()<<"\n";
}
return 0;
}
디버깅
사실 이 문제는 1년전에 풀어봤던 문제였는데 어느분의 테케 저격으로 실패된 것을 확인하고 다시 풀이를 시도해본 것입니다.
문제점은 경로를 역추적하는 부분에 있었습니다. 예를 들어, 한 지점에서 두갈래길로 나뉘고 그 경로가 한지점으로 다시 모이는 경우를 생각해볼 수 있습니다.
이런 경우 경로는 잘 맞게 체크가 되지만 역추적하는데 필요한 노드가 큐에 중복해서 추가 되는 문제가 발생합니다.
따라서, 이를 방지하기 위하여 최단경로 엣지를 true로 체크는 하되 이미 방문한 노드인 경우는 큐에 추가하지 않도록 변경하였습니다.
제출결과
40ms
마무리
최단경로 알고리즘을 이용하는 문제였습니다. 최단경로를 어떻게 제거할지에 대해 생각해야하는 문제로, 약간의 응용이 필요합니다.