백준 4386번 별자리 만들기 C++

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

 

모든 별끼리 서로 연결될 수 있기 때문에 이어질수 있는 모든 경로를 후보로 두고 거리가 작은 순서로 정렬한 뒤 최소 스패닝 트리를 이용하여 풀었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n;

struct Pos {
	int head;
	double x;
	double y;
};

struct LoadInfo {
	Pos start;
	Pos end;
	double dist;
	bool operator<(const LoadInfo& other) {
		return dist < other.dist;
	}
};

vector<Pos> parent;
vector<int> height;
vector<LoadInfo> loads;

double GetDist(const Pos& start, const Pos& end) {
	return sqrt(pow(start.x - end.x, 2) + pow(start.y - end.y, 2));
}

int GetParent(int n) {
	if (n == parent[n].head)
		return n;
	return parent[n].head = GetParent(parent[n].head);
}

void Merge(int u, int v) {

	u = GetParent(u);
	v = GetParent(v);

	if (u == v)
		return;

	if (height[u] > height[v])
		::swap(u, v);

	parent[u].head = v;

	if (height[u] == height[v])
		height[v]++;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	height = vector<int>(n, 1);
	for (int i = 0; i < n; i++) {
		double x, y;
		cin >> x >> y;
		parent.push_back({ i,x,y });
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j)
				continue;
			Pos start = parent[i];
			Pos end = parent[j];
			loads.push_back({ start,end,GetDist(start,end) });
		}
	}
	sort(loads.begin(), loads.end());
	double sum = 0;
	for (auto& a : loads) {
		if (GetParent(a.start.head) == GetParent(a.end.head))
			continue;
		Merge(a.start.head, a.end.head);
		sum += a.dist;
	}
	cout << fixed;
	cout.precision(2);
	cout << sum;
}