[백준 C++] 4386번: 별자리 만들기

1. 문제

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

4386번: 별자리 만들기

 

2. 알고리즘 분류

• 그래프 이론
• 최소 스패닝 트리

 

3. 소스 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <tuple>
#include <algorithm>

using namespace std;

int n, parent[101];
vector<pair<float, float>> stars;
vector<tuple<float, int, int>> graph;

// 부모를 찾는 함수
int Find(int x)
{
	return parent[x] == x ? x : parent[x] = Find(parent[x]);
}

// 2개의 노드를 한 그룹으로 묶는 함수
void Union(int a, int b)
{
	int pA = Find(a);
	int pB = Find(b);

	parent[pB] = pA;
}

// a와 b를 연결할 때, 그래프의 사이클이 발생하는지 체크하는 함수
bool is_cycle(int a, int b)
{
	int pA = Find(a);
	int pB = Find(b);

	if (pA == pB)
		return true;

	return false;
}

// 2개의 좌표의 거리를 구하는 함수
float get_dist(pair<float, float> a, pair<float, float> b)
{
	return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

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

	float ans = 0;

	// parent 초기화
	for (int i = 0; i < 101; i++)
		parent[i] = i;

	// 별의 개수(n) 입력
	cin >> n;
	
	// 별의 좌표 입력
	for (int i = 0; i < n; i++)
	{
		float x, y;
		cin >> x >> y;
		stars.push_back({ x, y });
	}

	// 이을 수 있는 모든 별의 경우의 수에 대해 거리를 계산해서 저장
	for (int i = 0; i < stars.size(); i++)
	{
		for (int j = 0; j < stars.size(); j++)
		{
			if (i == j) continue;

			float dist = get_dist(stars[i], stars[j]);
			graph.push_back(make_tuple(dist, i, j));
		}
	}

	// 거리를 기준으로 오름차순 정렬
	sort(graph.begin(), graph.end());

	// 크루스칼 알고리즘
	// 거리가 가장 낮은 순서부터 연결
	for (int i = 0; i < graph.size(); i++)
	{
		float dist = get<0>(graph[i]);
		int start = get<1>(graph[i]);
		int end = get<2>(graph[i]);

		// 싸이클이 발생하지 않을 경우에 연결
		if (!is_cycle(start, end))
		{
			Union(start, end);
			ans += dist;
		}
	}

	cout << ans;

	return 0;
}

 

4. 유용한 알고리즘

 1) Union-Find 함수

• 2개의 노드를 한 그룹으로 묶는 알고리즘

// 부모를 찾는 함수
int Find(int x)
{
	return parent[x] == x ? x : parent[x] = Find(parent[x]);
}

// 2개의 노드를 한 그룹으로 묶는 함수
void Union(int a, int b)
{
	int pA = Find(a);
	int pB = Find(b);

	parent[pB] = pA;
}

 

 2) Kruskal Algorithm

• 최소의 비용으로 그래프를 연결하는 알고리즘

// 거리를 기준으로 오름차순 정렬
sort(graph.begin(), graph.end());

// 크루스칼 알고리즘
// 거리가 가장 낮은 순서부터 연결
for (int i = 0; i < graph.size(); i++)
{
	float dist = get<0>(graph[i]);
	int start = get<1>(graph[i]);
	int end = get<2>(graph[i]);

	// 싸이클이 발생하지 않을 경우에 연결
	if (!is_cycle(start, end))
	{
		Union(start, end);
		ans += dist;
	}
}