[백준] 별자리 만들기 (C++)

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

 

좌표로 주어진 그래프를 노드그래프로 바꾼 후 크루스칼 알고리즘을 사용하면 쉽게 풀리는 문제.

 

다만 소수점을 주의해야한다.

 

크루스칼 알고리즘은 유니온 파인드와 그리디를 섞은 최소 스패닝 트리를 구할 수 있는 알고리즘이다.

 

#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;

pair<int, int> points[101];
vector<pair<int, pair<int, double>>> edges;
bool visited[101];
int par[101];

int Find(int x) {
    if(par[x] == x) return par[x];
    else return par[x] = Find(par[x]);
}

void Union(int x, int y){
    int px = Find(x);
    int py = Find(y);

    if(px < py) par[py] = px;
    else par[px] = py; 
}

bool comp(pair<int, pair<int, double>>& a, pair<int, pair<int, double>>& b) {
    return a.second.second < b.second.second;
}

int main() {
    int n; cin >> n;

    for(int i = 0; i < n; i++){
        par[i] = i;
        double x, y;
        cin >> x >> y;

        points[i].first = x;
        points[i].second = y;
    }

    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            double dist = sqrt(pow((points[i].first - points[j].first), 2) + pow((points[i].second - points[j].second), 2));
            edges.push_back({i, {j, dist}});
        }
    }

    sort(edges.begin(), edges.end(), comp);

    double ans = 0;
    for(int i = 0; i < edges.size(); i++){
        int x = edges[i].first;
        int y = edges[i].second.first;
        double d = edges[i].second.second;

        /* 다른그룹이면 합침 */
        if(Find(x) != Find(y)) {
            Union(x, y);

            ans += d;
        }
    }
    cout.precision(3);
    cout << ans << "\n";
}