C++[백준]2887번 행성 터널

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

2887번: 행성 터널

 

 

솔루션

---

처음에 https://www.acmicpc.net/problem/4386와 비슷해서 그대로 풀려고 했는데, 범위가 10만이라 무지성으로 했다간 시간초과를 받을 것 같았다.

 

그래서 조금 더 생각을 해 보니, 각각의 좌표를 정렬하여, 각각의 차를 모두 우선순위 큐에 넣어 준 뒤, MST 알고리즘을 수행하는 것이 좋아 보인다고 생각을 했고 성공을 했다.

 

 

먼저 각각의 좌표를 따로 따로 입력을 받는다. (인덱스 정보도 같이 둔다.)

각각을 좌표를 정렬 해 주고

우선순위 큐에 앞의 값과 차이를 배열에 담는다.

가장 차이가 작은 값 부터 유니온 파인드를 통해 연결 되었는지 안되었는지, 판별하고 연결한다.

 

 

코드

---

#define ll long long int
#define INF 987654321123
#define pint pair<int,int>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int parent[100002];
int getParent(int x) {
	if (x == parent[x]) return x;
	else return parent[x] = getParent(parent[x]);
}
void setUnion(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a > b) parent[a] = b;
	else parent[b] = a;
}
bool isUnion(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	return a == b;
}

pint axisX[100002];
pint axisY[100002];
pint axisZ[100002];
int N;


struct pa {
	int idx1, idx2;
	ll cost;
	bool operator<(const struct pa& t)const {
		if (cost == t.cost) {
			return idx1 > t.idx1;
		}
		return cost > t.cost;
	}
};
ll ans;
int cnt;
priority_queue<struct pa> pq;
void kruskal(void) {
	while (!pq.empty()) {
		int idx1 = pq.top().idx1;
		int idx2 = pq.top().idx2;
		ll cost = pq.top().cost;
		pq.pop();

		if (isUnion(idx1, idx2)) continue;
		setUnion(idx1, idx2);
		ans += cost;
	}
	return;
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> axisX[i].first;
		cin >> axisY[i].first;
		cin >> axisZ[i].first;
		axisX[i].second = axisY[i].second = axisZ[i].second = parent[i] = i;
	}
	sort(axisX, axisX + N);
	sort(axisY, axisY + N);
	sort(axisZ, axisZ + N);

	for (int i = 0; i < N - 1; i++) {
		pq.push({ axisX[i].second, axisX[i + 1].second ,abs(axisX[i].first - axisX[i + 1].first) });
		pq.push({ axisY[i].second, axisY[i + 1].second ,abs(axisY[i].first - axisY[i + 1].first) });
		pq.push({ axisZ[i].second, axisZ[i + 1].second ,abs(axisZ[i].first - axisZ[i + 1].first) });
	}

	kruskal();

	cout << ans << "\n";
}