BOJ 4386 | 별자리 만들기

최소 스패닝 트리를 그려서 해결하는 기초 문제다. 모든 별을 잇는 트리의 선분 길이를 출력하라는 문제인데 그냥 평범하게 구현해서 출력하자.

여기서는 간선의 비용이 아닌 정점의 좌표가 주어지므로 잘 가공해서 간선으로 만드는데 $O(N^2)$이 들고, $N = 100$이기 때문에 무리 없이 통과할 수 있다.

가벼운 마음으로 해결하자.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

class UnionFind{
private:
	vector<double> parent;
public:
	UnionFind(int n){
		parent.resize(n+1);
		for (int i = 0; i <= n; i++){ // parent[i] = i's parent
			parent[i] = i;
		}
	}
	int Find(int x){
		if (x == parent[x]) return x;
		return parent[x] = Find(parent[x]);
	}
	void Union(int x, int y){
		x = Find(x);
		y = Find(y);
		parent[y] = x;
	}
	vector<double> tree(){
		return parent;
	}
};

struct Node{
	int l, r;
	double w;
};

struct Dot{
	double x, y;
};

bool cmp(Node x, Node y){
	return x.w < y.w;
}

int main(){
	FASTIO;
	
	int N; cin >> N;
	UnionFind S = UnionFind(N);
	vector<Node> node;
	vector<Dot> dot; dot.push_back({0, 0});
	
	for (int i = 0; i < N; i++){
		double x, y; cin >> x >> y;
		dot.push_back({x, y});
	}
	
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++){
			if (i == j) continue;
			double dist = (dot[i].x - dot[j].x)*(dot[i].x - dot[j].x)+(dot[i].y - dot[j].y)*(dot[i].y - dot[j].y);
			node.push_back({i, j, sqrt(dist)});
		}	
	}
	
	sort(node.begin(), node.end(), cmp);
	
	double sum = 0;
	for (auto &i : node){
		if (S.Find(i.l) != S.Find(i.r)){
			S.Union(i.l, i.r);
			sum += i.w;
		}
	}
	
	printf("%.2f", sum);
	
}