[백준 C++] 2887 행성 터널 - 최소신장트리

2887번: 행성 터널

---

 

문제풀이

 

N-1개의 에지를 구성하는 최소 비용을 구하는 MST 유형의 문제입니다.

각 에지의 비용을 구할 때, 모든 행성끼리 연결해버리면 O($N^{2}$)으로 시간초과가 발생합니다.

따라서 행성들을 X값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개),

Y값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개),

Z값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개)를 구합니다.

이렇게 되면 3N-3개의 에지만으로 문제를 풀 수 있습니다.

위의 에지를 이용해서 기존의 MST 유형대로 최소 비용을 구하면 됩니다.

---

코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> p;
typedef pair<int, p> edge;

int N;
p PX[100000];
p PY[100000];
p PZ[100000];
priority_queue<edge, vector<edge>, greater<edge>> Edge;

int Root[100000];

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

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

void Union(int NodeA, int NodeB)
{
	int A = Find(NodeA);
	int B = Find(NodeB);
	int Min = min(A, B);
	Root[A] = Min;
	Root[B] = Min;
}

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

	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> PX[i].first >> PY[i].first >> PZ[i].first;
		PX[i].second = i;
		PY[i].second = i;
		PZ[i].second = i;
	}

	sort(PX, PX + N);
	sort(PY, PY + N);
	sort(PZ, PZ + N);

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

		Edge.emplace(abs(PX[i].first - PX[i + 1].first), p(PX[i].second, PX[i + 1].second));
		Edge.emplace(abs(PY[i].first - PY[i + 1].first), p(PY[i].second, PY[i + 1].second));
		Edge.emplace(abs(PZ[i].first - PZ[i + 1].first), p(PZ[i].second, PZ[i + 1].second));
	}

	int EdgeNum = 0;
	long long Weight = 0;
	while (!Edge.empty() && EdgeNum < N - 1)
	{
		int W = Edge.top().first;
		int A = Edge.top().second.first;
		int B = Edge.top().second.second;
		Edge.pop();
		if (Find(A) == Find(B))
		{
			continue;
		}

		Union(A, B);
		Weight += W;
		++EdgeNum;
	}

	cout << Weight;
}