BOJ 4386 별자리 만들기

www.acmicpc.net/problem/4386

4386번: 별자리 만들기

문제에서 가중치는 주어지지 않는다. 따라서 우리가 직접 가중치값을 설정해줘야 하는데

각 별의 위치를 받으면 \(O(N^2)\)으로 가중치를 쉽게 설정해줄 수 있다.

거리 공식은 \(\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}\) 이다.

 

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

struct P {
	int u, v;
	double w;
};
vector<P> ar;
vector<pair<double, double>> d;
vector<int> uf;
int n, cnt;
double ans;

int find(double x) {
	return uf[x] < 0 ? x : uf[x] = find(uf[x]);
}

bool merge(double x, double y) {
	x = find(x);
	y = find(y);
	if (x == y) return false;
	uf[y] = x;
	return true;
}

double cal(double x1, double y1, double x2, double y2) {
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n;
	uf.resize(n + 1, -1);
	d.resize(n);

	for (int i = 0; i < n; ++i) cin >> d[i].first >> d[i].second;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			double dist = cal(d[i].first, d[i].second, d[j].first, d[j].second);
			ar.push_back({ j,i,dist });
		}
	}

	sort(ar.begin(), ar.end(), [](const P& a, const P& b) { return a.w < b.w; });

	for (int i = 0;; ++i) {
		if (merge(ar[i].u, ar[i].v)) {
			ans += ar[i].w;
			if (++cnt == n - 1) break;
		}
	}

	cout << ans << endl;

	return 0;
}