[백준 C++] 4386 별자리 만들기 - 최소신장트리

4386번: 별자리 만들기

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

typedef pair<float, float> star;
typedef tuple<float, int, int> edge;

vector<star> Stars;
vector<edge> EdgeList;
int Root[100];

float MakeDistance(const star& A, const star& B)
{
	float AX = A.first, AY = A.second;
	float BX = B.first, BY = B.second;

	return sqrtf((AX - BX) * (AX - BX) + (AY - BY) * (AY - BY));
}

int Find(int Node)
{
	if (Node == Root[Node])
	{
		return Node;
	}

	return Root[Node] = Find(Root[Node]);
}

void Union(int A, int B)
{
	int RootA = Find(A);
	int RootB = Find(B);

	int NewRoot = min(RootA, RootB);
	Root[RootA] = NewRoot;
	Root[RootB] = NewRoot;
}

void Init(int N)
{
	Stars.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		float X, Y;
		cin >> X >> Y;
		Stars.emplace_back(X, Y);
	}

	EdgeList.reserve(N * N);
	for (int i = 0; i < N - 1; ++i)
	{
		for (int j = i + 1; j < N; ++j)
		{
			EdgeList.emplace_back(MakeDistance(Stars[i], Stars[j]), i, j);
		}
	}

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

	for (int i = 0; i < N; ++i)
	{
		Root[i] = i;
	}
}

float Kruskal(int N)
{
	int CntEdge = 0;
	float CntDistance = 0;
	while (CntEdge < N - 1)
	{
		for (int i = 0; i < EdgeList.size(); ++i)
		{
			int A = get<1>(EdgeList[i]);
			int B = get<2>(EdgeList[i]);

			if (Find(A) != Find(B))
			{
				Union(A, B);
				CntDistance += get<0>(EdgeList[i]);
				++CntEdge;
			}
		}
	}

	return CntDistance;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N;
	cin >> N;

	Init(N);

	cout << fixed;
	cout.precision(2);
	cout << Kruskal(N);
}

---

 

최소 신장 트리 유형의 문제로, 크루스칼 알고리즘을 이용해서 풀었습니다.

풀이 과정은 다음과 같습니다.

 

1. 에지 리스트로 그래프 구현 & 유니온 파인드 리스트 초기화 - 유니온 파인드를 통해 사이클 판별하기 위함
2. 에지 리스트를 가중치 오름차순으로 정렬
3. 가중치가 낮은 에지부터 연결 시도 - 파인드 연산을 통해 서로 다른 집합임을 판별했을 때(루트노드가 서로 다름)만 연결
4. N-1개의 에지가 연결될 때까지 3번 반복 -> 연결된 에지 개수 & 비용 합 카운트
5. 총 에지 비용 출력