[백준 4386] 별자리 만들기

문제 풀이

 

주어진 별들의 좌표가 주어질 때 최소한의 비용으로 모든 별들을 이어주면 되는 문제입니다.

기존에 풀어왔던 문제들은 (a 노드, b 노드, c 비용)으로 주어져서 edges에 저장하고, 간선들을 비용에 따라 오름차순으로 정렬하여 구현했지만,

 

이번에 주어지는 것은 2차원 평면 형태로 좌표로 주어집니다.

따라서 2차원 좌표를 (a 노드, b 노드, c 비용) 형태로 만든 후 문제를 해결하면 됩니다.

 

우선은 모든 좌료를 하나의 배열에 모두 넣어준 다음에 2중 for문을 만든 후

한 좌표에서 다른 좌표까지의 (두 점 사이의 거리)를 구해서 edges 배열에 넣어줍니다.

int size = static_cast<int>(stars.size()); // 별들의 좌표를 담은 배열
for (int i = 0; i < size; i++)
{
	for (int j = i + 1; j < size; j++)
	{
		double x1 = stars[i].first;
		double y1 = stars[i].second;
		double x2 = stars[j].first;
		double y2 = stars[j].second;
		double distance = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
		edges.push_back({ distance, {i + 1, j + 1} }); // (거리, (노드1, 노드2)) 연결 상태를 저장
	}
}

이렇게 edges를 만들었다면 거리를 오름차순으로 하여 정렬하고, 간선을 추가할 때마다 사이클이 발생하는지 안 하는지를 검사하여 별들을 이어주면 됩니다.

 

소스 코드

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

const int MAX = 101;
int parent[MAX];
vector<pair<double, pair<int, int> > > edges;
int N;

void input()
{
	cin >> N;
	vector<pair<double, double> > stars;
	for (int i = 0; i < N; i++)
	{
		double a, b;
		cin >> a >> b;
		stars.emplace_back(a, b);
	}

	int size = static_cast<int>(stars.size());
	for (int i = 0; i < size; i++)
	{
		for (int j = i + 1; j < size; j++)
		{
			double x1 = stars[i].first;
			double y1 = stars[i].second;
			double x2 = stars[j].first;
			double y2 = stars[j].second;
			double distance = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
			edges.push_back({ distance, {i + 1, j + 1} });
		}
	}

	sort(edges.begin(), edges.end());
	for (int i = 1; i <= N; i++) parent[i] = i;
}

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

void unionParent(int a, int b)
{
	a = findParent(a);
	b = findParent(b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

void solve()
{
	input();

	int size = static_cast<int>(edges.size());
	double ans = 0;
	for (int i = 0; i < size; i++)
	{
		double distance = edges[i].first;
		int a = edges[i].second.first;
		int b = edges[i].second.second;
		if (findParent(a) != findParent(b))
		{
			ans += distance;
			unionParent(a, b);
		}
	}

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}