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

백준의 네트워크 복구(2211) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

문제를 보고 가장 먼저 생각했던 방법은 '최소 스패닝 트리(Minimal Spanning Tree)' 를 구현하는 것이였다.

왜냐하면, '슈퍼컴퓨터를 통해서 다른 컴퓨터들로 통신이 가능하게끔 네트워크를 연결할 때, 그 시간이 최소가 되도록 하는 것' 이

그래프에서 '모든 노드를 포함하면서, 순환되는 경로가 없고 그 가중치가 가장 작은 트리'를 만드는 MST를 만드는 과정과

비슷하다고 생각했기 때문이다.

그런데 ! 단순 MST를 구현하게 되면 문제에 위배되는 조건이 하나 생기게 된다.

그 위배되는 조건은 두 번째 조건이다. 이 두 번쨰 조건에 대해서 간략하게만 이야기해보면 "슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소시간이, 원래의 네트워크 통신하는데 걸리는 시간보다 더 오래 걸리면 안된다" 이다.

아래와 같은 상황을 생각해보자. 컴퓨터가 4대가 있고, 5개의 통신망으로 연결된 상태이다.

위와 같은 형태로 입력이 주어졌다고 생각해보자. 위의 그래프를 MST로 구현했을 때의 형태를 그려보면 다음과 같다.

이런 경우가 우리가 말한 두 번째 조건에 위배되는 것이다.

위의 최소스패닝트리의 경우, 1번 정점에서 4번정점으로 가는데 걸리는 시간이 '6초'(1 → 2 → 4)가 된다.

그런데 초기 맵에서 1번 정점에서 4번정점으로 가는데 걸리는 시간은 '5초'였다. 즉 ! 슈퍼컴퓨터과 다른 컴퓨터들과 통신하는데

걸리는 시간이(6초), 원래의 네트워크 통신하는데 걸리는 시간(5초)보다 더 오래 걸리게 되는 것이다.

따라서, 단순 MST를 구현하면 올바른 정답을 구할 수가 없다.

그래서 본인은 1번정점에서 다른 모든 정점으로의 최소시간을 구하기 위해서 '다익스트라 알고리즘'을 사용하였다.

다익스트라 알고리즘에 대해서 모른다면 아래의 글을 읽고 오도록 하자.

[ 다익스트라 알고리즘 알아보기(Click) ]

다익스트라 알고리즘을 통해서 '1번정점(슈퍼컴퓨터)' 으로부터 다른 컴퓨터들로 가는데 걸리는 최소 시간을 구해주었다.

그럼 이 구현한 내용으로 어떻게 정답을 출력을 해야할지 이야기해보자.

먼저, '복구할 회선의 갯수' 를 구해보자. 이 갯수는 무조건 N - 1 개가 된다. 왜냐하면 N개의 컴퓨터가 있는데, 이 N개의 컴퓨터를

연결하기 위해서는 최소 N - 1개의 회선이 필요하기 때문이다. 즉 ! 복구할 회선의 갯수 K 는 N - 1 값이 된다.

그리고 그 복구한 회선의 정보를 표현해야한다. 이 부분을 위해서 본인은 'int Parent[]' 라는 배열을 하나 사용해주었다.

다익스트라 알고리즘을 구현할 때, 값이 갱신되는 과정(방문하려는 정점에 드는 비용이 지금 계산하는 비용보다 더 비싼경우)에서

값이 갱신된다면, Parent의 값을 설정해 주었다.

예를 들어서 1번정점에서 2번정점으로 가는데 걸리는 시간이 10초였는데, 1번정점에서 3번정점을 통해 2번정점으로 가는데 걸리는 시간이 5초가 된다면, 이 때 다익스트라 알고리즘에서는 값의 갱신이 발생한다. 그럼 이 경우에 ! 2번정점의 부모값을 '3번'정점으로 바꿔주는 것이다. 이와 같은 방식을 이용해서 구현하였다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N, M;
int Dist[MAX];
int Parent[MAX];
vector<pair<int, int>> V[MAX];
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        V[a].push_back(make_pair(b, c));
        V[b].push_back(make_pair(a, c));
    }
}
 
void Dijkstra(int Start)
{
    for (int i = 1; i <= N; i++) Dist[i] = 2e9;
    Dist[Start] = 0;
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, Start));
    
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        for (int i = 0; i < V[Cur].size(); i++)
        {
            int Next = V[Cur][i].first;
            int nCost = V[Cur][i].second;
 
            if (Dist[Next] > Cost + nCost)
            {
                Dist[Next] = Cost + nCost;
                Parent[Next] = Cur;
                PQ.push(make_pair(-Dist[Next], Next));
            }
        }
    }
}
 
void Solution()
{
    Dijkstra(1); 
    cout << N - 1 << endl;
    for (int i = 2; i <= N; i++)
    {
        cout << Parent[i] << " " << i << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}