4386 - 별자리 만들기

첫번째 시도

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;

double ans;
int parent[101];
int n;
vector<pair<double, pair<int, int>>> v;
vector<pair<double, pair<int, int>>> v1;

int getParent(int x) {
	if (parent[x]==x) {
		return x;
	}
	else {
		return parent[x] = getParent(parent[x]);
	}
}

void unionNode(int a, int b) {
	if (a > b) {
		swap(a, b);
	}
	parent[b] = a;
}

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

void Input() {
	double a, b;
	for (int i = 0; i < 101; i++) {
		parent[i] = i;
	}
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		v.push_back({ 0,{a,b} });
	}

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int x1 = v[i].second.first;
			int x2 = v[j].second.first;
			int y1 = v[i].second.second;
			int y2 = v[j].second.second;
			v1.push_back({ dist(x1,x2,y1,y2),{ i, j} });
		}
	}
	
	sort(v1.begin(), v1.end());

}

void sol() {
	for (int i = 0; i < v1.size(); i++) {
		if (getParent(v1[i].second.first) != getParent(v1[i].second.second)) {
			unionNode(getParent(v1[i].second.first), getParent(v1[i].second.second));
			ans += v1[i].first;
		}
	}
	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;
	cout.precision(2);

	Input();
	sol();
	return 0;
}

맞았지만 중간중간 가져갈 것들이 많다.

핵심

1. 유니온 파인드 이용
2. 브루트포스를 이용하여 모든 좌표와 좌표의 사이의 길이를 계산합니다. 그 과정에서 v1.push_back({ dist(x1,x2,y1,y2),{ i, j} }); 노드를 (x,y) -> (x1,y1)으로 이동한 것을 i, j로 간소화 시켜 저장할 수 있습니다.

• 주의! i+1, j+1로 저장하면 parent[]배열을 정확한 위치에서 관리할 수 있습니다.

3. vector<pair<double, pair<int, int>>> v; 이런식으로 저장하면 sort함수를 이용하여 정렬하면 v.first기준으로 정렬되므로 가중치 순으로 정렬을 쉽게 할 수 있다.
4. 소수점 둘째자리까지 표현

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