[백준 16398번] 행성 연결 (C++)

문제링크 : https://www.acmicpc.net/problem/16398

16398번: 행성 연결

#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct p
{
    int u, v, weight;
    bool operator<(p const &e) 
    {
        return weight < e.weight;
    }
};

int parent[1000];
vector<p>edge;

int find_root(int x)
{
    if(x == parent[x]) return x;
    return parent[x] = find_root(parent[x]);
}

bool Union(int a, int b)
{
    a=find_root(a);
    b=find_root(b);
    if(a!=b)
    {
        parent[a]=b;  //속한 트리가 다르면 병합
        return 1;
    }
    return 0;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            int num;
            cin >> num;
            if(i<j) //중복제외
            {
                edge.push_back({i, j, num});
            }
        }
    }

    sort(edge.begin(), edge.end());

    for(int i=0; i<N; i++)
    {
        parent[i]=i;
    }

    ll result = 0;
    int cnt =0;

    for(int i=0; edge.size(); i++)
    {
        p e = edge[i];
        if(Union(e.u, e.v))        //속한 트리가 다르면 
        {
            result += e.weight;    //가중치 더해줌
            cnt++;
            if(cnt == N-1) break;  //최소 간선의 수 일때
        }
    }

    cout << result << "\n";
    return 0;
}

가중치가 있는 최소 신장 그래프를 만드는 크루스컬 알고리즘 문제이다.

분리집합 문제에서 사용했던 유니온 파인드 알고리즘을 사용한다.