[최소 신장 트리 단계] 백준 4386번 별자리 만들기

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

반올림 반영하려면 ans = round(ans) 이렇게 갱신해야 함.

#include <iostream>
#include<vector>
#include <algorithm>
#include<cmath>
#include<queue>
using namespace std;

int parent[101];

int findParent(int node)
{
	if (parent[node] == node)
		return parent[node];
	return parent[node] = findParent(parent[node]);
}

pair<double, double> arr[101];
struct Node
{
	int start;
	int end;
	double cost;
};

bool compare(Node n1, Node n2)
{
	return n1.cost < n2.cost;
}
int main() {
	ios::sync_with_stdio(false);

	cin.tie(NULL);
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		double x, y;
		cin >> x >> y;
		arr[i] = { x,y };
		parent[i] = i;
	}

	vector<Node> vec;
	for (int i = 1; i <= N; i++)
	{
		for (int j = i + 1; j <= N; j++)
		{
			double cost = sqrt(pow((arr[i].first - arr[j].first), 2) + pow((arr[i].second - arr[j].second), 2));
			vec.push_back({ i,j,cost });
		}
	}
	sort(vec.begin(), vec.end(), compare);

	double ans = 0.0;
	for (int i = 0; i < vec.size(); i++)
	{
		int node1 = findParent(vec[i].start);
		int node2 = findParent(vec[i].end);
		if (node1 != node2)
		{
			parent[node2] = node1;
			ans += vec[i].cost;
		}
	}
	ans *= 100;
	ans = round(ans);
	ans /= 100;
	cout << (double)ans << "\n";
}