[백준 1647] 도시 분할 계획 - cpp로 구현한 최소 신장 트리

문제 개요

• 문제 번호: 1647
• 제목: 도시 분할 계획
• 난이도: 골드 4
• 링크: 백준 1647번

---

문제 설명

N개의 집이 있는데 연결되어있는 도로를 없애 N개의 집들을 2개의 마을 집단으로 분할해야한다.

---

접근 방법

도로를 지우는 것이 아닌 주어지는 M개의 도로에서 비용이 적은 도로를 선택한다.

이때 마을1과 마을2는 서로 도로가 연결 되어 있으면 안된다. 즉 처음에 N개의 집을 각각의 집합으로 지정하고 도로를 연결할때 마다 집합을 합하여 2개의 집합으로 만들면 된다.

이때 사용되는 알고리즘은 Union-Find를 이용한 크루스칼 알고리즘을 이용한다. 

---

구현 코드

#include<iostream>
#include<tuple>
#include<algorithm>
using namespace std;

int n, m;
tuple<int, int, int> edge[1000005];
int p[100005];

int find(int x){
    if(p[x] == x) return x;
    return p[x] = find(p[x]);
}

bool is_diff_group(int a, int b){
    a = find(a);
    b = find(b);

    if( a == b) return 0;
    else if(a < b) p[b] = a;
    else p[a] = b;
    return 1;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        p[i] = i;

    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        edge[i] = {c, a, b};
    }

    sort(edge, edge + m);

    int u = n;
    int ans = 0;
    for(int i = 0; i < m; i++){
        if(u == 2) break;
        int c, a, b;
        tie(c, a, b) = edge[i];

        if(!is_diff_group(a, b)) continue;
        ans += c;
        u--;
    }

    cout << ans;
}