๐ฃ ๋ฌธ์ ์ดํด
x, y, z ์ขํ๋ก ํ์ฑ์ ์์น๊ฐ ์ฃผ์ด์ง๊ณ (๋ ธ๋), ๊ทธ ํ์ฑ๋ค ์ฌ์ด์ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ค์น๊ฐ ๋๋ค(๊ฐ์ ).
ํ์ฑ๊ณผ ํ์ฑ ์ฌ์ด์ ๊ฑฐ๋ฆฌ๋ ๋ฌธ์ ์ ์ฃผ์ด์ง ์กฐ๊ฑด์ฒ๋ผ min(abs(x1-x2), abs(y1-y2), abs(z1-z2))๊ฐ ๋๋ค.
์ด ๋ฌธ์ ๋ ํฌ๋ฃจ์ค์นผ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ์ดํ๋ค.
๐ญ ํ์ด ๊ณผ์
์์ฑ ์ธ์ด: C++
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
class Planet {
public:
int x, y, z, index;
Planet(int x, int y, int z, int index) {
this->x = x;
this->y = y;
this->z = z;
this->index = index;
}
};
class Tunnel {
public:
int start, dest, cost;
Tunnel(int start, int dest, int cost) {
this->start = start;
this->dest = dest;
this->cost = cost;
}
};
int planet_cnt = 0;
int result = 0;
const int MAX = 100001;
vector<Planet>planets;
vector<Tunnel>tunnels;
int parent[MAX] = {0, };
bool compare_x(const Planet &p1, const Planet &p2) {
return p1.x < p2.x;
}
bool compare_y(const Planet &p1, const Planet &p2) {
return p1.y < p2.y;
}
bool compare_z(const Planet &p1, const Planet &p2) {
return p1.z < p2.z;
}
bool compare_cst(const Tunnel &t1, const Tunnel &t2) {
return t1.cost < t2.cost;
}
int getCost(const Planet p1, const Planet p2) {
int x_dist = abs(p1.x - p2.x);
int y_dist = abs(p1.y - p2.y);
int z_dist = abs(p1.z - p2.z);
return min(x_dist, min(y_dist, z_dist));
}
int getParent(int node) {
if (node == parent[node]) return node;
return parent[node] = getParent(parent[node]);
}
void mergeTree(int node1, int node2) {
int node1_p = getParent(node1);
int node2_p = getParent(node2);
parent[node1_p] = node2_p;
}
int main() {
cin >> planet_cnt;
for (int i = 0; i < planet_cnt; ++i) {
int x, y, z;
cin >> x >> y >> z;
planets.push_back(Planet(x, y, z, i));
}
for (int i = 0; i < planet_cnt; ++i) {
parent[i] = i;
}
sort(planets.begin(), planets.end(), compare_x);
for (int i = 0; i < planet_cnt-1; ++i)
tunnels.push_back(Tunnel(planets[i].index, planets[i+1].index, getCost(planets[i], planets[i+1])));
sort(planets.begin(), planets.end(), compare_y);
for (int i = 0; i < planet_cnt-1; ++i)
tunnels.push_back(Tunnel(planets[i].index, planets[i+1].index, getCost(planets[i], planets[i+1])));
sort(planets.begin(), planets.end(), compare_z);
for (int i = 0; i < planet_cnt-1; ++i)
tunnels.push_back(Tunnel(planets[i].index, planets[i+1].index, getCost(planets[i], planets[i+1])));
sort(tunnels.begin(), tunnels.end(), compare_cst);
for (int i = 0; i < tunnels.size(); ++i) {
if (getParent(tunnels[i].start) != getParent(tunnels[i].dest)) {
result += tunnels[i].cost;
mergeTree(tunnels[i].start, tunnels[i].dest);
}
}
cout << result << endl;
return 0;
}
์ผ๋ฐ์ ์ธ ์ต์ ์ ์ฅ ํธ๋ฆฌ ๋ฌธ์ ์ ๋น์ทํ์ง๋ง, ํ์ฑ๊ณผ ํ์ฑ์ ์ฐ๊ฒฐํ๋ ๋ชจ๋ ๊ฒฝ๋ก๋ฅผ ์ ์ฅํ๋ฉด ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค.
๋ฐ๋ผ์ x์ถ, y์ถ, z ์ถ์ผ๋ก ๋ฐ๋ก ์ธ์ ํ ํ์ฑ๋ค๋ผ๋ฆฌ์ ๊ฒฝ๋ก๋ง ์ ์ฅํ๋ฉด ๋ฌธ์ ์์ด ํด๊ฒฐํ ์ ์๋ค.