[백준][C++] 2307 도로검문

www.acmicpc.net/problem/2307

2307번: 도로검문

 

 

 

알고리즘 종류

    - 다익스트라

 

 

 

사고 과정

    1. 검문을 하지 않을 때, 최단경로를 구한다.

        1-1. 최단 경로를 저장한다. 저장하는 방법은 parents 배열을 이용해서 부모 노드를 기록한다.

 

    2. 최단 경로에 있는 노드를 막고, 다익스트라를 수행한다.

        2-1. 구해진 최단 경로 비용이 무한대이면, -1 출력

        2-2. 구해진 최단 경로 비용 - 검문하지 않은 최단 경로 비용 출력

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#define MAX 987654321
 
using namespace std;
 
 
int n, m;
int answer=0;
bool first=true;
 
vector<vector<pair<int, int> > > edges;
vector<int> dp; // 시간을 기록  
vector<int> parents; // 노드의 부모를 기록하여, 최단 경로 기록하기  
 
void dijkstra(int node1, int node2){
    
    priority_queue<pair<int, int> > pq; // cost, node
    dp[1] = 0;
    pq.push({0, 1});
    
    while(!pq.empty()){
        int here = pq.top().second;
        int time = -pq.top().first;
        pq.pop();
        
        if(time > dp[here]) continue;
        if(here==n) return;
        
        for(int i=0; i<edges[here].size(); i++){
            int next = edges[here][i].first;
            int next_time = time + edges[here][i].second;
            
            if((node1==here && node2==next) || (node2==here && node1==next)) continue;
            
            if(dp[next] > next_time){
                if(first) parents[next] = here; // 검문 안 할 때, 최단 경로 기록하기  
                dp[next] = next_time;
                pq.push({-next_time, next});
            }
        }
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    
    // 초기화  
    parents.resize(n+1);
    edges.resize(n+1);
    dp.resize(n+1);
    for(int j=0; j<=n; j++) dp[j] = MAX;
    
    int a,b,c;
    for(int i=0; i<m; i++){
        cin >> a >> b >> c;
        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }
    
    parents[1]=1;
    dijkstra(0, 0);
    first=false;
    int standard = dp[n]; // 검문 없을 때 시간  
    
    // 검문할 간선 선택  
    for(int p=n; p!=parents[p]; p=parents[p]){
        for(int j=0; j<=n; j++) dp[j] = MAX;
        
        int node1 = p;
        int node2 = parents[p];
        
        dijkstra(node1, node2);
        
        if(dp[n]==MAX){
            cout << -1 << endl;
            return 0;
        }
        answer = max(answer, dp[n] - standard);
    }
    
    cout << answer << endl;
}

 

 

 

시행착오

    - 1차로 풀었을 때는, 시간복잡도  MMlogM으로 풀었다. 통과는 했지만, 시간이 오래걸렸다. 방법을 생각하던 중에, 최단 경로의 간선들만 검문하면 된다는 것을 뒤늦게 깨달았다. 그런데, 최단 경로의 간선들을 어떻게 기록할까? 노드가 연결되어 있다는 것을 기록하는 방법은 union_find 알고리즘을 생각하면 될 것 같다. parents라는 1차원 배열에 부모 값을 저장했다. 그래서 마지막에는 자기 자신이 저장된다.