[MST(최소 신장트리)] 크루스칼 알고리즘과 예제 문제2: 별자리 만들기 (+ 소수점 자리 조절)

별자리 만들기_백준

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

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

struct cmp {
	bool operator() (const pair<pair<int, int>, double>& p1, pair<pair<int, int>, double>& p2) {
		return p1.second > p2.second;	// 간선 거리가 짧은 순으로 우선되도록
	}
};

int N;
vector<pair<double, double>> STARS(100);

class UF {
private:
	vector<int>* parentTablePtr;
public:
	UF(int numOfNode) {
		vector<int>* vecPtr = new vector<int>(numOfNode + 1);
		for (int i = 1; i <= numOfNode; i++) {
			(*vecPtr)[i] = i;
		}
		parentTablePtr = vecPtr;
	}
	~UF() {
		delete parentTablePtr;
	}

	bool UNION(int nodea, int nodeb) {
		int parenta = FIND(nodea);
		int parentb = FIND(nodeb);

		if (parenta == parentb)
			return false;

		if (parenta < parentb)
			(*parentTablePtr)[parentb] = parenta;
		else
			(*parentTablePtr)[parenta] = parentb;

		return true;
	}

private:
	int FIND(int node) {
		if ((*parentTablePtr)[node] == node)
			return node;
		else
			return (*parentTablePtr)[node] = FIND((*parentTablePtr)[node]);
	}
};


double solution() {
	// nC2의 조합으로 두 개의 별간의 거리 구한 후 우선순위 큐에 담기
	priority_queue<pair<pair<int, int>, double>, vector<pair<pair<int, int>, double>>, cmp> pq;
	for (int i = 0; i < N-1; i++) {
		for (int j = i + 1; j < N; j++) {
			double nowX = STARS[i].first;
			double nowY = STARS[i].second;
			double nextX = STARS[j].first;
			double nextY = STARS[j].second;

			double len = sqrt(pow(nowX - nextX, 2) + pow(nowY - nextY, 2));
			pq.push({ {i, j}, len });
		}
	}

	int numOfSelectedEdge = 0;
	double sumOfEdge = 0;
	UF uf(N);
	while (!pq.empty()) {
		pair<pair<int, int>, double> edge = pq.top(); pq.pop();
		int nodea = edge.first.first;
		int nodeb = edge.first.second;
		double cost = edge.second;

		if (uf.UNION(nodea, nodeb)) {
			sumOfEdge += cost;
			numOfSelectedEdge++;
		}
		
		if (numOfSelectedEdge == N - 1)
			break;
	}

	return sumOfEdge;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		double x, y;
		cin >> x >> y;
		STARS[i] = { x, y };
	}

	double answer = solution();
	cout << fixed;
	cout.precision(2);
	cout << answer << '\n';
}