백준 소스코드 [C++] 2887 행성 터널

www.acmicpc.net/problem/2887

2887번: 행성 터널

백준 소스코드 [C++] 2887 행성 터널

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <sstream>
#include <cstdlib>
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
typedef long long ll;
using namespace std;

int E, dz,dy, dx, w;

struct Edge {
	int cost, node[2];
	Edge(int u,int v,int cost) {
		this->cost = cost;
		this->node[0] = u;
		this->node[1] = v;
	}
	bool operator<(Edge e) {
		return this->cost < e.cost;
	}
};

struct Dot {
	int z,y, x,idx;
	Dot(int z, int y, int x,int idx) {
		this->z = z;
		this->y = y;
		this->x = x;
		this->idx = idx;
	}
	int cost(Dot h) {
		return min({ abs(this->x - h.x),abs(this->y - h.y) ,abs(this->z - h.z) });
	}
};

bool compareX(Dot L, Dot R) {
	return L.x < R.x;
}

bool compareY(Dot L, Dot R) {
	return L.y < R.y;
}

bool compareZ(Dot L, Dot R) {
	return L.z < R.z;
}

vector <Edge> edges;
vector <int> Parent, Rank;
vector <Dot> dots;

int findParent(int u){
	if (Parent[u] == u) return u;
	return Parent[u] = findParent(Parent[u]);
}

void mergeParent(int u, int v){
	u = findParent(u);
	v = findParent(v);
	if (u == v)return;
	if (Rank[u] > Rank[v]) swap(u, v);
	Parent[u] = v;
	if (Rank[u] == Rank[v]) Rank[v]++;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> E;
	Rank.resize(E, 1);
	Parent.resize(E);

	for (int i = 0;i < E;i++)Parent[i] = i;

	for (int i = 0;i < E;i++) {
		cin >> dx >> dy >> dz;
		dots.push_back(Dot(dz,dy,dx,i));
	}

	sort(all(dots), compareX);
	for (int i = 0;i < E - 1;i++) edges.push_back(Edge(dots[i].idx, dots[i + 1].idx, dots[i].cost(dots[i + 1])));

	sort(all(dots), compareY);
	for (int i = 0;i < E - 1;i++) edges.push_back(Edge(dots[i].idx, dots[i + 1].idx, dots[i].cost(dots[i + 1])));
	
	sort(all(dots), compareZ);
	for (int i = 0;i < E - 1;i++) edges.push_back(Edge(dots[i].idx, dots[i + 1].idx, dots[i].cost(dots[i + 1])));

	sort(all(edges));
	int res = 0;
	for (int i = 0;i < (int)edges.size();i++) {
		int cost = edges[i].cost;
		int L = edges[i].node[0];
		int R = edges[i].node[1];
		if (findParent(L) == findParent(R))continue;
		mergeParent(L, R);
		res += cost;
	}
	cout << res;
	return 0;
}