BOJ 2887 - 행성터널

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

2887번: 행성 터널

 

특이하게 행성 간 간선으 비용이 min(x,y,z)이다.

모든 두 정점(n*n-1)에 대해서 최소값을 찾아가면서 간선을 두면 n이 1e5라 시간초과가 난다.

 

x,y,z값과 각각의 행성 번호를 쌍으로 갖는 배열을 세 개 만들어서 정렬한다면 한 정점에 대해서 가장 가까운 정점은 6가지가 된다. 따라서 MST를 구하고자 할 때 모든 간선을 잇고 MST를 구하지 않고 한 정점 당 6개의 정점만 이어줘도

MST를 구했을 때 결과값이 바뀌지 않을 것이다.

#include <iostream>
#include <algorithm>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int, int> P;

P x[100001], y[100001], z[100001];
int uf[100001];

int find(int a) {
	if (uf[a] == -1) return a;
	return uf[a] = find(uf[a]);
}

bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return false;
	uf[a] = b;
	return true;
}

struct Edge {
	int u, v, w;
	Edge(int u1, int v1, int w1) :u(u1), v(v1), w(w1) {}
	bool operator < (const Edge& A) const { return w < A.w; }
};

int main() {
	ios_base::sync_with_stdio(false);
	int n; cin >> n;
	vector<Edge> e;

	for (int i = 0, a, b, c; i < n; i++) {
		cin >> a >> b >> c;
		x[i] = { a,i }, y[i] = { b,i }, z[i] = { c,i };
	}

	sort(x, x + n);
	sort(y, y + n);
	sort(z, z + n);
	for (int i = 0; i < n - 1; i++) {
    	int dist = x[i + 1].first - x[i].first;
		e.push_back(Edge(x[i].second, x[i + 1].second, dist));
	}
	for (int i = 0; i < n - 1; i++) {
		int dist = y[i + 1].first - y[i].first;
		e.push_back(Edge(y[i].second, y[i + 1].second, dist));
	}
	for (int i = 0; i < n - 1; i++) {
		int dist = z[i + 1].first - z[i].first;
		e.push_back(Edge(z[i].second, z[i + 1].second, dist));
	}
	sort(e.begin(), e.end());
	fill(uf, uf + 100001, -1);
	long long sum = 0;
	int cnt = 0;
	for (int i = 0; i < e.size(); i++) {
		if (merge(e[i].u, e[i].v)) {
			sum += e[i].w;
			if (++cnt == n - 1) break;
		}
	}
	cout << sum << '\n';
}