[백준/BOJ] 백준 4386번 : 별자리 만들기

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

4386번: 별자리 만들기

 

각 별들 사이 길이를 재서, 간선을 만들고, 해당 간선을 통해 최소 스패닝 트리를 만들어 문제를 해결했다.

 

코드

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

int n;
vector<pair<double, double>> star;
vector<tuple<double, int, int>> edge; //(별 사이 거리,별1,별2);

int parent[105];
int rank_size[105];

void pre() {
	for (int i = 0; i < 105; i++) {
		parent[i] = i;
		rank_size[i] = 1;
	}
}

double dist(pair<double, double> u, pair<double, double> v) {
	return sqrt(((u.first - v.first) * (u.first - v.first)) + ((u.second - v.second) * (u.second - v.second)));
}

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

void merge(int u, int v) {
	u = find(u);
	v = find(v);

	if (u == v) {
		return;
	}

	if (rank_size[u] < rank_size[v]) {
		parent[u] = v;
	}
	else {
		parent[v] = u;
		if (rank_size[u] == rank_size[v]) {
			rank_size[u]++;
		}
	}
}

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

	pre();

	cin >> n;

	for (int i = 0; i < n; i++) {
		double x, y;
		cin >> x >> y;
		star.push_back(make_pair(x, y));
	}

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			double cost = dist(star[i], star[j]);
			edge.push_back(make_tuple(cost, i, j));
		}
	}

	sort(edge.begin(), edge.end());

	int cnt = 0;
	double result = 0;
	for (int i = 0; i < edge.size(); i++) {
		double cost = get<0>(edge[i]);
		int u = get<1>(edge[i]);
		int v = get<2>(edge[i]);

		u = find(u);
		v = find(v);

		if (u != v) {
			merge(u, v);
			result += cost;
			cnt++;
		}

		if (cnt == n - 1) { //모두 다 연결 되었을때
			break;
		}
	}

	cout << fixed;
	cout.precision(2);
	cout << result;

	return 0;
}