[백준 1922] 네트워크 연결

0. 제목

• 백준 1922 네트워크 연결
• BOJ 1922 네트워크 연결
• C++ 1922 네트워크 연결

---

1. 문제

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

---

2. 풀이

• Union-Find 방식을 사용하였다.
• find는 root를 찾아주는 함수이고 merge는 서로 다른 집합에 있을 때 하나의 집합으로 합쳐주는 함수이다.
• comp는 가중치를 기준으로 하여 오름차순으로 정렬되도록 설정하는 함수이다.
• main함수에서는 edge들 정보를 입력받고 가중치를 기준으로 오름차순 정렬을 한다.
• 그 후 입력받은 노드들이 같은 집합에 있는지를 판단하여 같은 집합에 있지 않으면 하나의 집합으로 합쳐주며 길이를 더해준다.
• 그 과정을 반복하면 모든 컴퓨터를 연결하는데 필요한 최소비용이 나온다.

---

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int parent[1001];
 
struct edge{
    int u, v, weight;
    edge(int u, int v, int weight){
        this->u = u;
        this->v = v;
        this->weight = weight;
    }
};
 
int find(int u){
    if(u == parent[u])
        return u;
    return parent[u] = find(parent[u]);
}
 
void merge(int u, int v){
    u = find(u);
    v = find(v);
    
    parent[u] = v;
}
 
int comp(edge &a, edge &b){
    return a.weight < b.weight;
}
 
int main(int argc, const char * argv[]) {
    int N, M;
    vector<edge> v;
    
    cin >> N >> M;
    for(int i = 1; i <= N; i++)
        parent[i] = i;
    
    int a, b, c;
    for(int i = 0; i < M; i++){
        cin >> a >> b >> c;
        v.push_back(edge(a, b, c));
    }
    
    sort(v.begin(), v.end(), comp);
    
    int ans = 0;
    for(int i = 0; i < M; i++){
        if(find(v[i].u) != find(v[i].v)){
            merge(v[i].u, v[i].v);
            ans += v[i].weight;
        }
    }
    cout << ans << '\n';
    return 0;
}