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

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 최소 신장 트리(MST) 문제로, 모든 노드(== 별)에서 다른 모든 노드로 향하는 간선이 있다고 가정하고, 이 간선들에 대해 크루스칼 알고리즘을 사용하여 모든 노드들이 이어지되, 이어지는 간선들의 가중치의 합이 최소가 되는 경우를 구해야 한다.

1) pair(노드의 x좌표, y좌표)들을 저장하는 nodes 벡터에 각 노드의 x좌표와 y좌표를 입력받아 저장한다.

2) 모든 노드들 사이에 존재하는 간선에 대한 tuple(두 노드 간 가중치, 노드A 번호, 노드B 번호)들을 저장하는 벡터인 edges에 모든 노드에서 다른 모든 노드로 향하는 간선에 대한 가중치를 계산해 저장한다.

• 계산은 calcDist() 함수에서 피타고라스 정리를 이용해 계산한다.

3) edges 벡터에 대해 크루스칼 알고리즘을 적용한다.

• 모든 노드들에 대한 사이클 테이블이 자기 자신을 가리키도록 한다.
• edges를 가중치의 오름차순으로 정렬한다.
• edges에 저장된 모든 간선에 대해 해당 간선에 연결된 노드A와 노드B를 비교(find)한다.
  • 두 노드의 부모가 같으면 (같은 그래프에 존재하면) 다음 간선으로 넘어간다.
  • 두 노드의 부모가 다르면 (같은 그래프에 존재하지 않으면)
    • 두 노드의 부모를 번호가 작은 쪽의 부모로 합친다. (union)
    • answer에 가중치를 누적시킨다.

4) 위 크루스칼 알고리즘 과정이 끝나면 소수점을 2자리로 제한시켜 answer를 출력한다.

🖥️ 풀이 코드

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

using namespace std;
typedef tuple<float, int, int> tfii;
typedef pair<float, float> pff;

int parent[100];

int getParent(int n)
{
	if (parent[n] == 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[b] = a;
	else
		parent[a] = b;
}

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

	return (a == b);
}

vector<pff> nodes;

// 별들 사이 거리 계산
float calcDist(pff a, pff b)
{
	return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

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

	int n;
	cin >> n;

	// nodes에 각 별들에 대한 pair(x, y) 저장
	for (int i = 0; i < n; i++)
	{
		float x, y;
		cin >> x >> y;
		nodes.push_back(pff(x, y));
	}

	// edges에 모든 간선에 대한 tuple(별들 간 비용, 별A, 별B) 저장
	vector<tfii> edges;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i != j)
			{
				float cost = calcDist(nodes[i], nodes[j]);
				edges.push_back(tfii(cost, i, j));
			}
		}
	}

	// 크루스칼 알고리즘
	for (int i = 0; i < n; i++)
		parent[i] = i;

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

	float answer = 0;
	for (int i = 0; i < edges.size(); i++)
	{
		int curA = get<1>(edges[i]);
		int curB = get<2>(edges[i]);

		if (!findParent(curA, curB))
		{
			unionParent(curA, curB);
			answer += get<0>(edges[i]);
		}
	}

	// 소수점 2자리로 제한
	cout << fixed;
	cout.precision(2);
	cout << answer;
}