[BOJ] 5719번 - 거의 최단 경로

백준 5719번 - 거의 최단 경로

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	15875	2326	1428	19.538%

문제

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

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

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 10^4)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N) 다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ 10^3) 이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다. U에서 V로 가는 도로는 최대 한 개이다. 또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.

---

예제 입력 1

7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
0 0

예제 출력 1

5
-1
6

출처

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

5719번: 거의 최단 경로

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 다익스트라

접근 방법

접근 방법 자체는 어려운 것이 없다. 단, 신경 써야 할 부분들이 좀 있었다.

먼저 처음으로 최단 경로를 구한다음, 최단 경로들 상에 존재하는 모든 Edge들을 제거한다.

이 후, 최단 거리를 다시 구하는 방법으로 쉽게 접근할 수 있다.

 

점 -> 점 간의 최단경로를 구하는 과정과 각 도로의 길이 P 가 양수인 점을 감안하여, 다익스트라를 이용하여 최단 경로를 구한다.

이 때, 테스트 케이스의 수가 정해지지 않았으므로 Priority Queue를 이용하여 최적화 된 다익스트라 알고리즘(O((V+E)logE)을 사용한다.

다익스트라 알고리즘이 최단 거리를 갱신할 때, 해당 노드를 방문하기 바로 직전 노드를 pre배열에 저장해놓으면

임의의 점 i에 대하여 최단 경로를 구하기 위해 i부터 이전 노드까지 DFS를 통해 역순으로 방문하며 경로를 구할 수 있다.

( 최단 경로가 여러개가 존재할 수 있으므로, pre는 배열로 저장한다 ) 

이렇게 역순으로 방문할 때, 사이클이 존재하게 되는 경우 무한루프에 빠질 수 있다는 것을 유의하자. 이를 방지하기 위해 방문한 정점들을 기록해두므로서 사이클을 처리하였다.

이렇게 최단 경로를 따라가면서 존재하는 모든 엣지들을 지우는 방법으로 Masking을 이용하였다. 이 때 Edge의 cost는 양수라는 조건이 붙어있으므로, 절대 존재할 수 없는 -1 값을 가중치로 둠으로서 해당 간선으로 방문하는 것을 원천적으로 막을 수 있도록 다익스트라 알고리즘에 추가적으로 조건을 주었다.

 

다익스트라 알고리즘을 정확하게 잘 이해하고 있다면, 최단 경로를 구하는 방법도 그다지 어렵지는 않을 것이다.

필자는, 다익스트라 알고리즘 내부에서 dist[next] == dist[current] + currentToNext 값일 때도 Priority Queue에 원소를 추가하여 메모리 초과를 받았았다. 

다익스트라를 위한 우선순위 큐 내부에서 탐색을 중복해서 처리하는 경우이다. dist[next] == dist[current] + currentToNext인 상황에서는 이미 이전에, 최단 거리를 갱신한 적이 있고 다른 경로를 통해서 방문한 current 또한 최단 거리를 가지는 경우이다. 

이 경우에 이전에 방문한 경로만 추가해주는 것이 메모리 측면에서 효율적이다. current 이후로의 경로는 동일하기 때문이다.

Priority Queue에 {dist[next], next} 를 넣어주면, 이 과정에서 제한된 메모리를 훨씬 넘겨버리는 케이스가 위 문제에서 존재했다.

 

소스 코드

#define DELETED (-1)
#include <bits/stdc++.h>
using namespace std;
int N, M, S, D;
int dijkstra(vector<pair<int,int>> *adj, vector<int> *pre, int start, int dest){
    vector<int> dist(N, 1e9);

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> PQ;
    dist[start] = 0;
    PQ.push({0, start});

    while(!PQ.empty()){
        auto top = PQ.top(); PQ.pop();
        int acDist = top.first, current = top.second;
        if( acDist < dist[current] )
            continue;
        for(auto edge : adj[current]){
            int currentToNext = edge.first;
            int next = edge.second;
            if( currentToNext == DELETED )
                continue;
            if( dist[current] + currentToNext < dist[next] ){
                dist[next] = dist[current] + currentToNext;
                pre[next].clear();
                pre[next].push_back(current);
                PQ.push({dist[next], next});
            }
            else if( dist[current] + currentToNext == dist[next] ){
                pre[next].push_back(current);
            }
        }
    }
    return dist[dest];
}
void deleteEdges(vector<pair<int,int>> *adj, vector<int> *pre, bool *visited, int current){
    // 사이클 존재 시 무한 루프 방지
    if( visited[current] ) return;
    visited[current] = true;
    for(auto prev: pre[current]){
        for(int i=0; i<adj[prev].size(); i++) {
            if( adj[prev][i].second == current ){
                adj[prev][i].first = DELETED;
                deleteEdges(adj, pre, visited, prev);
            }
        }
    }
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    while(true){
        cin >> N >> M;
        if( N == 0 && M == 0 ) break;
        cin >> S >> D;
        vector<pair<int,int>> adj[501];
        for(int i=0; i<M; i++){
            int u, v, p;
            cin >> u >> v >> p;
            adj[u].push_back({p, v});
        }
        vector<int> pre[501];
        dijkstra(adj, pre, S, D);
        bool visited[501] = {false, };
        deleteEdges(adj, pre, visited, D);
        int ans = dijkstra(adj, pre, S, D);
        if(ans == 1e9) ans = -1;
        cout << ans << '\n';
    }

    return 0;
}