백준 4386 별자리 만들기 (c++) : 피너클

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

4386번: 별자리 만들기

최소 스패닝 트리 문제다.

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

사용할 변수다.

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

find함수다. num의 조상을 반환한다.

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	parent[u] = v;
}

merge함수다. u와 v를 합친다.

double c(int i, int j) {
	return sqrt(pow(v[i].first - v[j].first, 2) + pow(v[i].second - v[j].second, 2));
}

c함수다. v[i]와 v[j]의 거리를 반환한다.

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

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

이제 값들 입력받으며 parent를 초기화한뒤

solve()를 출력하면 된다. fixed와 precision(2)는 소수점 2자리까지 출력하기 위해 사용한다.

double solve() {
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			edges.push_back({ c(i, j), {i, j} });
		}
	}
	sort(edges.begin(), edges.end());

solve함수다.

먼저 모든 간선을 edges에 담고 정렬한다.

	double ans = 0;
	for (int i = 0; i < edges.size(); i++) {
		double cost = edges[i].first;
		int u = edges[i].second.first, v = edges[i].second.second;

		if (find(u) == find(v)) continue;
		ans += cost;
		merge(u, v);
	}
	return ans;
}

그후 edegs의 크기만큼 반복문을 돌린다.

cost는 u와 v를 연결하는 비용이다.

만약 u와 v의 조상이 같다면 뒤를 무시하고

아니면 ans에 cost를 더한뒤 두 정점을 연결한다.

반복문이 끝나면 ans를 반환하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

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

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

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (u == v) return;
	parent[u] = v;
}

double c(int i, int j) {
	return sqrt(pow(v[i].first - v[j].first, 2) + pow(v[i].second - v[j].second, 2));
}

double solve() {
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			edges.push_back({ c(i, j), {i, j} });
		}
	}
	sort(edges.begin(), edges.end());

	double ans = 0;
	for (int i = 0; i < edges.size(); i++) {
		double cost = edges[i].first;
		int u = edges[i].second.first, v = edges[i].second.second;

		if (find(u) == find(v)) continue;
		ans += cost;
		merge(u, v);
	}
	return ans;
}

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

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

	cout << fixed;
	cout.precision(2);
	cout << solve() << endl;
}

전체코드다.