[C++] 별자리 만들기 - 4386

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

using namespace std;

// 그냥 함수로 빼도 되지만 묶어서 정리하고 싶어서 class로 만듬
class UF // Union_Find
{
public:
	static int FindParent(int parent[], int n)
	{
		if (parent[n] == n) return n;
		return parent[n] = FindParent(parent, parent[n]);
	}

	static void UnionParent(int parent[], int a, int b)
	{
		a = FindParent(parent, a);
		b = FindParent(parent, b);
		if (a < b) parent[b] = a;
		else parent[a] = b;
	}

	static bool GetParent(int parent[], int a, int b)
	{
		if (FindParent(parent, a) == FindParent(parent, b)) return false;
		else return true;
	}
};



class Edge // 간선
{
public:
	Edge(int a, int b, float d) {
		Node[0] = a;
		Node[1] = b;
		distance = d;
	}
	bool operator < (Edge& edge)
	{
		return this->distance < edge.distance;
	}
public:
	int Node[2];
	float distance;
};


int main()
{
	vector<Edge> v; // 간선
	vector<pair<int, int>> pv; // 별자리 좌표
	int parent[101]{ 0 };
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		float a, b;
        // 모든 노드는 자기 자신을 가르키는걸로 초기화
		parent[i] = i; 
		cin >> a >> b;
		pv.push_back(make_pair(a, b)); // 좌표를 넣음
	}

	for (int i = 0; i < N - 1; i++)
	{
		for (int j = i + 1; j < N; j++)
		{
			float dist = static_cast<float>(
				sqrt(pow(pv[j].first - pv[i].first, 2) +
				pow(pv[j].second - pv[i].second, 2)));
                // 거리 계산후 노드와 거리를 vector에 넣음
			v.push_back(Edge(i, j, dist));
		}
	}
	sort(v.begin(), v.end()); // 거리가 짧은 순으로 정렬

	float sum = 0;
	for (int i = 0; i < v.size(); i++)
	{
		if (UF::GetParent(parent, v[i].Node[0], v[i].Node[1]))
		{
			sum += v[i].distance;
			UF::UnionParent(parent, v[i].Node[0], v[i].Node[1]);
		}// 순환되지 않으면 묶음
	}

	
	cout << round(sum * 100) / 100;

	return 0;
}