득이공간
[백준 C++] 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;
}
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 3190 뱀 - 덱 (0) | 2024.04.21 |
---|---|
[백준 C++] 16566 카드 게임 - 분리집합 (1) | 2024.04.19 |
[백준 C++] 2565 전깃줄 - 다이나믹프로그래밍 (0) | 2024.04.17 |
[백준 C++] 9328 열쇠 - 너비우선탐색 (0) | 2024.04.13 |
[백준 C++] 2263 트리의 순회 - 트리 (0) | 2024.04.12 |