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

이 문제는 최소 스패닝 트리 문제이다.

 

별의 개수 n개의 최대는 100이므로, O(N^2) 으로 모든 간선을 만들 수 있다.

 

모든 별들을 잇는 대신에, 직/간접적으로 이어저야한다. 이는 최소 스패닝 트리를 의미하므로, 크루스칼 알고리즘을 사용해서 문제를 풀었다.

 

절대/상대 오차를 10^(-2) 까지 허락하므로 cout << fixed; cout.precision(2); 를 사용해서 소숫점 두번째 자릿수까지 출력하면 정답이 나온다.

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

int n;
vector<pair<double, double>> stars;
struct Edge {
	int a;
	int b;
	double dist;
};
vector<Edge> edges;
int parent[100];

bool compare(Edge &a, Edge &b) {
	return a.dist < b.dist;
}

void init() {
	for (int i = 0; i < 100; i++) {
		parent[i] = i;
	}
}

int find(int x) {
	if (parent[x] != x) {
		return parent[x] = find(parent[x]);
	}
	return x;
}

bool merge(int a, int b) {
	a = find(a);
	b = find(b);

	if (a == b) {
		return false;
	}

	if (a < b) {
		parent[b] = a;
	} else {
		parent[a] = b;
	}
	return true;
}

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		double x, y;
		cin >> x >> y;

		stars.push_back({ x, y });
	}

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			pair<double, double> &s1 = stars[i];
			pair<double, double> &s2 = stars[j];

			double x = s1.first - s2.first;
			double y = s1.second - s2.second;

			double dist = sqrt(x * x + y * y);
			
			edges.push_back({ i, j, dist });
		}
	}

	sort(edges.begin(), edges.end(), compare);
}

double solve() {
	double result = 0;

	for (Edge &edge : edges) {
		int a = edge.a;
		int b = edge.b;
		double dist = edge.dist;

		if (merge(a, b)) {
			result += dist;
		}
	}

	return result;
}

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

	init();
	input();
	cout << fixed;
	cout.precision(2);
	cout << solve() << '\n';

	return 0;
}