[BOJ 4386 // C++] 별자리 만들기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 4386번 문제인 별자리 만들기이다.
문제는 아래 링크를 확인하자.

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

4386번: 별자리 만들기

주어진 별 N개에 대하여 서로 다른 별 사이에 두 별 사이 거리를 가중치로 하는 에지를 갖는 완전그래프를 생각해보자.

 

이 때, 문제에서 구하는 별자리의 가중치는 이 완전그래프의 MST(minimum spanning tree; 최소 신장 트리)의 가중치와 같게 된다. 이를 구현하여 문제를 해결하자. 글쓴이는 Kruskal 알고리즘을 이용하여 문제를 해결했다.

 

아래는 제출한 소스코드이다.

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

struct point {
	double x, y;
	point() {
		this->x = this->y = 0;
	}
	point(double x, double y) {
		this->x = x, this->y = y;
	}
};

struct edge {
	int x, y;
	double dist;
	edge(int x, int y, double dist) {
		this->x = x, this->y = y, this->dist = dist;
	}
};

bool comp(edge e1, edge e2) {
	return e1.dist < e2.dist;
}

point points[100];
vector<edge> edges;

int uf[100];
int findf(int x) {
	if (x == uf[x]) return x;
	return uf[x] = findf(uf[x]);
}

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

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

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		double x, y; cin >> x >> y;
		points[i] = point(x, y);
		for (int j = 0; j < i; j++) {
			double dist = sqrt((points[i].x - points[j].x) * (points[i].x - points[j].x) + (points[i].y - points[j].y) * (points[i].y - points[j].y));
			edges.emplace_back(edge(j, i, dist));
		}
	}
	sort(edges.begin(), edges.end(), comp);

	for (int i = 0; i < N; i++) uf[i] = i;

	double ans = 0;
	for (auto e : edges) {
		int x = e.x, y = e.y;
		int fx = findf(x), fy = findf(y);
		if (fx == fy) continue;
		ans += e.dist;
		uf[fy] = fx;
	}

	cout << ans;
}