BOJ 4386 별자리 만들기

1 개요

BOJ 4386 별자리 만들기

• 백준 온라인 저지 4386번 문제
• BOJ 37단계

2 C++

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

int n;
int parent[101];
vector<pair<float,float>> loc;
vector<pair<float,pair<int,int>>> star;

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

void Union(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if(a != b) parent[a] = b;
}

void solve() {
    float x_a, y_a, x_b, y_b, distance;
    for(int i=0; i<loc.size() ; i++) {
        x_a = loc[i].first;
        y_a = loc[i].second;
        for(int j = i + 1 ; j < loc.size() ; j++){
            x_b = loc[j].first;
            y_b = loc[j].second;
            distance = sqrt(pow((x_b-x_a),2) + pow((y_b-y_a),2));
            star.push_back({distance, {i+1, j+1}});
        }
    }
    sort(star.begin(), star.end());
    for(int i=1; i<=n; i++) {
        parent[i] = i;
    }
    float answer = 0;
    for(int i=0; i<star.size(); i++) {
        int a = star[i].second.first;
        int b = star[i].second.second;
        if(getParent(a) == getParent(b)) continue;
        Union(a, b);
        answer += star[i].first;
    }
    cout << answer;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    float x, y;
    for(int i=0; i<n ; i++) {
        cin >> x >> y;
        loc.push_back({x, y});
    }
    solve();
}