[백준] 2211: 네트워크 복구

0. 문제 주소

 

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

2211번: 네트워크 복구

 

 

1. 풀이

 

매우 국어 문제.

 

두 가지 조건을 보자.

 

 

해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다. 물론, 그렇다면 아무 회선도 복구하지 않으면 되겠지만, 이럴 경우 네트워크의 사용에 지장이 생기게 된다. 따라서 네트워크를 복구한 후에 서로 다른 두 컴퓨터 간에 통신이 가능하도록 복구해야 한다.

 

이 조건만 보고 대충 풀면 MST로 접근하게 된다. 두번째 조건을 보자.

 

 

 

네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

 

슈퍼컴퓨터는 1번 노드에 설치된다.

 

네트워크를 복구한 뒤 1번 노드에서 다른 모든 노드로 가는 최소 시간이, 원래 그래프에서의 그것보다 커져서는 안 된다.

 

다시 말해서, 원래 그래프의 1번 노드에서 다른 노드로 가는 최단 경로들만으로 이루어진 그래프가 복구하는 방법이라는 것이다.

 

예제도 MST인 것처럼 잘 해놨는데.. 문제에 나온 예제와 새로 만든 예시를 비교해보자.

 

 

 

프림 알고리즘으로 MST를 구한 것과 결과는 같아 보인다.

 

이번엔 (2, 4)의 가중치를 2에서 5로 바꿔서 동일하게 MST를 구해보자.

 

 

이 예시의 정답은 아래와 같다.

 

 

 

MST로 구했을 때를 보면, 1번 노드에서 4번 노드로 가는 시간이 5가 걸리지만, 원래 그래프에서는 4의 시간으로도 갈 수 있었다.

 

이는 두 번째 조건에 위배되므로, 프림 알고리즘을 통한 방법은 해답이 아님을 알 수 있다.

 

따라서 [PS/ShortestPath] - [BOJ] 5719: 거의 최단 경로와 같은 방법으로,

 

다른 모든 노드로부터 1번 노드까지 거슬러 올라가며 해당 간선이 최단 경로에 포함되는지를 체크해주면 된다.

 

시간을 더 줄이는 방법으로는, 다익스트라 알고리즘을 돌릴 때, 특정 노드 next의 dist가 갱신이 될 때마다

 

next 직전에 왔던 노드가 무엇인지 저장해두는 previ 배열을 이용하면 된다. 아래 코드는 이 방법으로 풀었다.

 

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

#define pii pair<int, int>
#define MAX 1005
#define INF 987654321

using namespace std;

int N, M;
vector<pii> graph[MAX];
priority_queue<pii, vector<pii>, greater<pii>> PQ;
int dist[MAX];
bool visited[MAX];
int previ[MAX];

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d %d", &N, &M);
    int u, v, w;
    for (int i=0;i<M;i++){
        scanf("%d %d %d", &u, &v, &w);
        graph[u].push_back(pii(v, w));
        graph[v].push_back(pii(u, w));
    }
    
    fill(dist+1, dist+N+1, INF);
    dist[1] = 0;
    PQ.push(pii(0, 1));
    while(!PQ.empty()){
        auto p = PQ.top();
        PQ.pop();
        int curr = p.second, curr_dist = p.first;
        if (visited[curr]) continue;
        visited[curr] = true;
        for (auto pp: graph[curr]){
            int next = pp.first, weight = pp.second;
            if (dist[next] > curr_dist + weight){
                previ[next] = curr;
                dist[next] = curr_dist + weight;
                PQ.push(pii(dist[next], next));
            }
        }
    }
    
    vector<pii> ans;
    int ans_cnt = 0;
    for (int i=1;i<=N;i++){
        if (previ[i] != 0){
            ans_cnt++;
            ans.push_back(pii(i, previ[i]));
        }
    }
    printf("%d\n", ans_cnt);
    for (auto p: ans){
        printf("%d %d\n", p.first, p.second);
    }

    

    return 0;
}