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

2887번: 행성 터널

---

 

문제풀이

 

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

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

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

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

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

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

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

---

코드

cpp

#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;
}