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

문제 링크입니다. https://www.acmicpc.net/problem/2211

2211번: 네트워크 복구

다익스트라를 사용해서 푸는 문제였습니다.

1번 점부터 시작해, 2~N번 점까지 각각 최소비용으로 선을 연결시키는 문제입니다.

최소 비용으로 연결했을 때, 복구한 선의 갯수와, 복구된 선을 구해야합니다.

 

문제에서 선을 복구하는 조건이 있습니다.

1. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한다. 물론, 그렇다면 아무 회선도 복구하지 않으면 되겠지만, 이럴 경우 네트워크의 사용에 지장이 생기게 된다. 따라서 네트워크를 복구한 후에 서로 다른 두 컴퓨터 간에 통신이 가능하도록 복구해야 한다.
2. 네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

1번 조건으로 보면, 최소 스패닝 트리를 사용해야 되지만, 2번 조건 때문에 다익스트라 알고리즘으로 풀어야 됨을 알 수 있습니다.

 

복구해야될 최소 간선의 갯수는 바로 알 수 있습니다.

N개의 정점을 연결하기 위해서는 N-1개의 간선이 필요하기 때문입니다.

그렇다면 2번부터 N번 정점까지는 연결된 하나의 간선이 복구되었다는 의미와 같을 것입니다.

 

다익스트라 알고리즘을 1번 정점부터 시작해서 탐색을 완료했을 때, X번 정점과 X번 정점의 부모를 알 수만 있으면 됩니다.

 

따라서 parent 배열을 이용해, X번 정점을 탐색하기 전의 정점을 저장해줬습니다.

 

마지막에 해당 배열을 통해 2번부터 N번 정점까지 출력해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define PP pair<int, P>
#define F first
#define S second
#define INF 987654321

using namespace std;

int N, M;
vector<P> connect[1001];
int Distance[1001];
int parent[1001];

void reset_distance(){
    for(int i = 1; i <= N; i++){
        Distance[i] = INF; 
    }
}

void Dijstra(int start){
    priority_queue<P> q; // cost, node, cnt
    q.push({-0, start});
    Distance[1] = 0;
    while(!q.empty()){
        int x = q.top().S;
        int cost = -q.top().F;
        q.pop();
        if(Distance[x] < cost) continue;
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i].F;
            int n_cost = cost + connect[x][i].S;
            if(Distance[xx] > n_cost){
                Distance[xx] = n_cost;
                parent[xx] = x;
                q.push({-n_cost, xx});
            }
        }
    }
}

void solve(){
    reset_distance();
    Dijstra(1);
    cout << N-1 << "\n";
    for(int i = 2; i <= N; i++){
        cout << parent[i] << " " << i << "\n";
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        int x, y, cost;
        cin >> x >> y >> cost;
        connect[x].push_back({y, cost});
        connect[y].push_back({x, cost});
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요!