[백준][C++] 2406 안정적인 네트워크

www.acmicpc.net/problem/2406

2406번: 안정적인 네트워크

 

 

 

알고리즘 종류

MST

 

 

사고 과정

1번 본사는 모든 지사와 연결되어 있기 때문에 제외합니다. 그러면 나머지 노드들을 가지고 MST를 진행하면 됩니다.

 

입력에서 이미 연결된 노드들이 주어지므로 union_find으로 두 노드의 부모 노드를 합쳐주는 것이 편합니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, m;
 
vector<vector<int> > conn;
vector<pair<int, pair<int, int> > > edges;
int mat[1001][1001];
int parents[1001];
 
 
bool cmp(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b){
    return a.first < b.first;
}
 
int get_parent(int a){
    if(parents[a] == a) return a;
    return parents[a] = get_parent(parents[a]);
}
 
void union_parents(int a, int b){
    a = get_parent(a);
    b = get_parent(b);
    
    if(a > b) parents[b] = a;
    else parents[a] = b;
}
 
void solution(){
    
    sort(edges.begin(), edges.end(), cmp);
    
    int sum = 0;
    vector<pair<int, int> > v;
    
    for(int i=0; i<edges.size(); i++){
        
        int node1 = edges[i].second.first;
        int node2 = edges[i].second.second;
        
        if(get_parent(node1) != get_parent(node2)){
            union_parents(node1, node2);
            v.push_back({node1, node2});
            sum += edges[i].first;
        }
    }
    
    if(v.size() == 0) cout << 0 << " " << 0 << endl;
    else {
        cout << sum << " " << v.size() << endl;
        for(int i=0; i<v.size(); i++){
            cout << v[i].second << " " << v[i].first << endl;
        }
    }
}
 
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    conn.resize(n+1);
    for(int i=2; i<=n; i++) parents[i] = i;
    
    // 이미 연결된 간선 추가하기  
    int a, b;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        if(get_parent(a) != get_parent(b)){
            union_parents(a,  b);
        }
    }
    
    // 간선 정보 받기  
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> mat[i][j];
        }
    }
    
    for(int i=2; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            edges.push_back({mat[i][j],{i, j}});
        }
    }
    
    solution();
}

 

 

 

시행착오