백준 2406 안정적인 네트워트

문제 링크

이 문제는 1번 노드를 제외하고 나머지 노드들을 연결하는 문제이다.

MST를 구성하면 되는데 MST를 구성하는 방법은 2가지 이다.

• 크루스칼 알고리즘
• 프림 알고리즘

이 중 크루스칼 방법이 구현이 쉽기 때문에 먼저 고려를 하였는데 조건에 만족하기 때문에 크루스칼로 구현했다.

크루스칼은 간선을 오름차순으로 정렬하여 연결 여부를 선택하는데 문제에서 간선의 수는 최대 10,000이므로 유효한 방법이다.

MST 구현을 위한 union-find를 구현하고 크루스칼로 풀었다

#include<bits/stdc++.h>

using namespace std;

int n, m; //n : 컴퓨터 수, m : 연결 수
int parent[1'001];

struct INFO{
    int from, to, dist;

    INFO(int from, int to, int dist) : from(from), to(to), dist(dist) {}

    bool operator<(const INFO& a) const{
        return dist > a.dist;
    }
};

vector<INFO> ans;

int findParent(int a){
    if(parent[a] == a) return a;
    return parent[a] = findParent(parent[a]);
}

void unionGroup(int a, int b){
    a = findParent(a);
    b = findParent(b);
    
    if(a == b) return;

    parent[a] = b;
}

bool isUnion(int a, int b){
    return findParent(a) == findParent(b);
}

int main(){
    priority_queue<INFO> pq;
    
    cin >> n >> m;
    for(int i = 1; i <= n;i++) parent[i] = i;

    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        unionGroup(x, y);
    }
    
    for(int i = 1; i <= n;i++){
        for(int j = 1; j <= n;j++){
            int distance;
            cin >> distance;
            if(i == 1 || j == 1 || i==j) continue;
            pq.push(INFO(i, j, distance));
        }
    }
    while(!pq.empty()){
        INFO cur = pq.top();
        pq.pop();
        if(isUnion(cur.from, cur.to)) continue;
        unionGroup(cur.from, cur.to);
        ans.push_back(cur);
    }
    int cnt = 0;
    for(INFO info : ans){
        cnt += info.dist;
    }
    cout << cnt << " " << ans.size() << endl;
    for(int i = 0; i < ans.size();i++){
        cout << ans[i].from << " " << ans[i].to << endl;
    }
    return 0;
}