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

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <math.h>
 
int n = 0;
int parent[101] = {};
double ans = 0;
std::vector<std::pair<double, double>> star = {};
std::vector<std::tuple<double, int, int>> edge = {};
 
double FindDistance(double x1, double y1, double x2, double y2)
{
    double dx = (x1 - x2) * (x1 - x2);
    double dy = (y1 - y2) * (y1 - y2);
 
    return sqrt(dx + dy);
}
 
int FindParent(int x)
{
    if (x == parent[x]) 
        return x;
 
    else 
        return parent[x] = FindParent(parent[x]);
}
 
bool SameParent(int x, int y)
{
    x = FindParent(x);
    y = FindParent(y);
 
    if (x == y)
        return true;
 
    else
        return false;
}
 
void Union(int x, int y)
{
    x = FindParent(x);
    y = FindParent(y);
 
    parent[y] = x;
}
 
int main()
{
    std::cout << std::fixed;
    std::cout.precision(2);
 
    std::cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        double x = 0;
        double y = 0;
        std::cin >> x >> y;
 
        star.push_back({ x,y });
    }
 
    for (int i = 0; i < star.size(); ++i)
    {
        double x1 = star[i].first;
        double y1 = star[i].second;
 
        for (int j = i + 1; j < star.size(); ++j)
        {
            double x2 = star[j].first;
            double y2 = star[j].second;
 
            double Dist = FindDistance(x1, y1, x2, y2);
 
            edge.push_back({ Dist, i, j });
        }
    }
 
    for (int i = 0; i < n; ++i)
    {
        parent[i] = i;
    }
 
    sort(edge.begin(), edge.end());
 
    for (int i = 0; i < edge.size(); ++i)
    {
        double cost = std::get<0>(edge[i]);
        int x = std::get<1>(edge[i]);
        int y = std::get<2>(edge[i]);
 
        if (!SameParent(x, y))
        {
            Union(x, y);
            ans = ans + cost;
        }
    }
 
    std::cout << ans;
 
    return 0;
}
 

 

모든 점들을 받아서 모든 선분을 만듭니다.

그 이후로 선들을 짧은 순서대로 정렬을 하고 순서대로 이어줍니다.

이 때 가장 짧은 선을 부모로 만들어서 이 선분에 연결해서 모두 이어놓습니다.

이미 이어져있다면 연결하지 않고 연결이 되어있지 않다면 선분의 길이를 추가하고 연결합니다.