[BOJ] 4386번 별자리 만들기 (C++)

문제 (https://www.acmicpc.net/problem/4386)

4386번: 별자리 만들기

최소 비용으로 모든 점을 연결하는 MST 알고리즘을 사용한 문제이다. Union-find를 사용하는 크루스칼 알고리즘으로 문제를 해결했다.

이 문제에서는 점 사이의 거리가 주어지지 않고 별의 좌표가 각각 주어지기 때문에 주어진 좌표들로 점 사이의 거리를 구해주었다. (Line 50~61)

위에서 구한 점 사이의 거리들을 바탕으로 최소 스패닝 트리를 구한다.

---

[소스코드]

	/*
	BOJ 4386번: 별자리 만들기
	2021-12-29
	Kruskal Algorithm
	*/
	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <math.h>
	#define MAX 101
	using namespace std;
	vector<pair<double, double>> coordinate;
	vector<pair<double, pair<double, double>>> edge;
	int parent[MAX];
	int getParent(int x) {
	if(parent[x] == x) return x;
	return parent[x] = getParent(parent[x]);
	}
	void unionParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if(a < b) parent[b] = a;
	else parent[a] = b;
	}
	int findParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if(a == b) return 1;
	else return 0;
	}
	int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	double ans = 0;
	int n;
	cin >> n;
	for(int i = 0 ; i < n ; i++) {
	double x, y;
	cin >> x >> y;
	coordinate.push_back({x, y});
	}
	for(int i = 0 ; i < coordinate.size() ; i++) {
	double x_a = coordinate[i].first;
	double y_a = coordinate[i].second;
	for(int j = i + 1 ; j < coordinate.size() ; j++){
	double x_b = coordinate[j].first;
	double y_b = coordinate[j].second;
	double distance = sqrt(pow((x_b - x_a), 2) + pow((y_b - y_a), 2));
	edge.push_back({distance, {i + 1, j + 1}});
	}
	}
	sort(edge.begin(), edge.end());
	for(int i = 1 ; i <= n ; i++) parent[i] = i;
	for(int i = 0 ; i < edge.size() ; i++) {
	int a = edge[i].second.first;
	int b = edge[i].second.second;
	double c = edge[i].first;
	if(findParent(a, b)) continue;
	unionParent(a, b);
	ans += c;
	}
	cout << ans;
	return 0;
	}

view raw 4386.cpp hosted with ❤ by GitHub

---

2021-12-29

Gold 4

- 그래프 이론

- 최소 스패닝 트리