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

4386번: 별자리 만들기

 

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

풀이

지금까지 MST 문제를 prim 알고리즘을 사용해 풀어왔으나 메모리 사용량이나 수행 시간을 봤을 때 kruskal 알고리즘이 더 효율적이라고 생각되어 이번에는 kruskal 알고리즘을 사용하여 구현해보았습니다.

 

익숙한 알고리즘이 아닌지라 다른 분들의 블로그에서 도움을 받았습니다.

---

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

using namespace std;

#define endl '\n'

int n;
double ans = 0;
int parent[100];
vector<pair<double, double>> loc;
vector<pair<double, pair<int, int>>> star;

void input()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		double x, y;
		cin >> x >> y;

		loc.push_back({ x, y });
	}
}

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

void unionParent(int a, int b)
{
	a = getParent(a);
	b = getParent(b);

	if (a != b)
		parent[a] = b;
}

bool findParent(int a, int b)
{
	a = getParent(a);
	b = getParent(b);

	if (a == b) return true;
	return false;
}

double getDistance(double x, double y, double xx, double yy)
{
	double dx = (x - xx) * (x - xx);
	double dy = (y - yy) * (y - yy);

	return sqrt(dx + dy);
}

void kruskal()
{
	for (int i = 0; i < n; ++i)
		parent[i] = i;

	for (int i = 0; i < n - 1; ++i)
	{
		double x = loc[i].first;
		double y = loc[i].second;

		for (int j = i + 1; j < n; ++j)
		{
			double xx = loc[j].first;
			double yy = loc[j].second;

			double distance = getDistance(x, y, xx, yy);
			star.push_back({ distance, {i, j} });
		}
	}

	sort(star.begin(), star.end());

	for (int i = 0; i < star.size(); ++i)
	{
		int starA = star[i].second.first;
		int starB = star[i].second.second;
		double distance = star[i].first;

		if (!findParent(starA, starB))
		{
			ans += distance;
			unionParent(starA, starB);
		}
	}
}

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

	input();
	kruskal();

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

	return 0;
}​