[백준 2211] 네트워크 복구 C++

2211번: 네트워크 복구

다익스트라

---

최소 스패닝 트리의 탈을 쓴 다익스트라 문제였다.

 

끊어진 그래프에서 최소 개수의 회선만을 복구해야 한다고 하길래 n-1개의 간선을 연결시켜서 모든 컴퓨터를 연결해 주는 MST 문제로 착각했다.

 

 

위 그래프에서 MST는 어떻게 될지 생각해보자

2-3, 2-4, 1-3 간선이 모여서 MST를 이룰 수 있다.

하지만 이 때 1 -> 2로가는 비용은 5가 되고, 1 -> 4로 가는 비용은 7이 된다.

각각 기존의 최단거리였던 4, 3 보다 커지게 되어 '원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.' 라는 문제의 조건에 어긋나게 된다.

따라서 MST 알고리즘은 이 문제에 적용시킬 수 없다.

 

다익스트라를 통해서 그래프를 한번 훑게 되면 하나의 스패닝 트리가 나오게 된다.

이는 루트에서 시작해 모든 정점까지의 거리가 최소가 되는 스패닝 트리가 된다.

따라서 다익스트라를 수행하면서 최단거리에 포함되는 간선들을 임의의 벡터에 저장하면 답을 구할 수 있다.

<+57, +58> 참조

 

 

알고리즘 분류를 끄고 문제를 푸니 생각을 더 많이 할 수 있어서 너무 좋은 것 같다. 👍

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
struct T{
    int cost, ed, prev;
};
 
struct cmp{
    bool operator()(T &a, T &b){
        return a.cost > b.cost;
    }
};
 
int N, M;
vector<pii > adj[1001];
vector<pii > rebuild;
int dist[1001];
 
void input(){
    cin >> N >> M;
    int a, b, c;
    for(int i = 0; i < M; i++){
        cin >> a >> b >> c;
        adj[a].push_back({c, b});
        adj[b].push_back({c, a});
    }
    for(int i = 1; i <= N; i++){
        dist[i] = INF;
    }
}
 
void Dijkstra(){
    priority_queue<T, vector<T>, cmp> que;
    que.push({0, 1, 0});
    dist[1] = 0;
    
    int prev = 1;
    
    while(!que.empty()){
        T now = que.top();
        que.pop();
        
        if(now.cost > dist[now.ed]) continue;
        
        if(now.prev){
            rebuild.push_back({now.prev, now.ed});
        }
        
        for(int i = 0; i < adj[now.ed].size(); i++){
            int next = adj[now.ed][i].second;
            int next_cost = adj[now.ed][i].first + now.cost;
            
            if(next_cost < dist[next]){
                dist[next] = next_cost;
                que.push({next_cost, next, now.ed});
            }
        }
    }
}
 
void solve(){
    Dijkstra();
    
    cout << rebuild.size() << "\n";
    for(auto &w : rebuild){
        cout << w.first << " " << w.second << "\n";
    }
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}