[ Problem Solving :: 백준 ] 4386 / 별자리 만들기

# Link

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

4386번: 별자리 만들기

 

 

# Code - C++

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <cmath>

using namespace std;

#define endl '\n'
#define len(x) (int)(x).length()
#define size(x) (int)(x).size()
#define str(x) to_string(x)
#define error logic_error("line " + str(__LINE__))

// Set up : Definitions
const int MAX = 100;
struct Point { double x, y; };
struct Edge { int fr, to; double dist; };

// Set up : Global Variables
int P[MAX], R[MAX];

// Set up : Functions Declaration
bool operator < (const Edge &u, const Edge &v);
int find(int x);
void merge(int x, int y);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int n; cin >> n;
    Point S[n];
    for (int i=0; i<n; i++)
        cin >> S[i].x >> S[i].y;

    // Process
    for (int i=0; i<n; i++) {
        P[i] = i;
        R[i] = 1;
    }

    vector<Edge> E(n*(n-1)/2);
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            double dx = S[i].x - S[j].x;
            double dy = S[i].y - S[j].y;
            double dist = sqrt(dx*dx + dy*dy);
            E.push_back({i, j, dist});
        }
    }

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

    int cnt = 0;
    double ans = 0;
    for (auto [fr, to, dist] : E) {
        if (find(fr) == find(to)) continue;
        merge(fr, to);
        cnt++, ans += dist;
        if (cnt == n-1) break;
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
bool operator < (const Edge &u, const Edge &v)
{
    auto ut = make_tuple(u.dist, u.fr, u.to);
    auto vt = make_tuple(v.dist, v.fr, v.to);
    return ut < vt;
}

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

void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y) return;

    if (R[x] < R[y]) { swap(x, y); }

    P[y] = x;

    if (R[x] == R[y]) { R[x]++; }
}

 

 

지적, 조언, 첨언 모두 환영합니다!!!