[백준/BOJ] 4386 별자리 만들기

문제 : 4386 별자리 만들기

4386번: 별자리 만들기

별들의 좌표가 주어졌을 때 각 별들을 모두 잇는

최소 길이를 구해 출력하는 문제이다.

최소 스패닝 트리를 구해야 하므로 UnionFind를 짜고

각 간선에 이어진 점과 간선의 비용을 우선순위 큐에 넣어

가장 적은 비용부터 꺼내며 사이클이 생기지 않게 처리해주면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<double,double> pdd;
struct ABC{
    ll a, b;
    double x;
    ABC(){}
    ABC(ll a, ll b, double x): a(a), b(b), x(x){}
};
bool operator<(ABC a, ABC b){
    return a.x > b.x;
}
ll N, MST[105];
double ans=0;
vector<pdd> arr;
priority_queue<ABC> pq;
ll Find(ll x){
    if (x==MST[x]) return x;
    return MST[x]=Find(MST[x]);
}
void Union(ll x, ll y){
    MST[Find(x)]=Find(y);
}
int main(){
    cin >> N;
    for (int i=0;i<100;i++){
        MST[i]=i;
    }
    for (int i=0;i<N;i++){
        double a, b;
        cin >> a >> b;
        arr.push_back({a,b});
    }
    for (int i=0;i<N;i++){
        for (int j=i+1;j<N;j++){
            double len=sqrt(pow(arr[i].first-arr[j].first,2)+pow(arr[i].second-arr[j].second,2));
            pq.push(ABC(i,j,len));
        }
    }
    while (!pq.empty()){
        ABC now=pq.top();
        pq.pop();
        if (Find(now.a)==Find(now.b))
            continue;
        Union(now.a,now.b);
        ans+=now.x;
    }
    printf("%.2f", ans);
    return 0;
}