2887 planet tunnel
์๊ณ ๋ฆฌ์ฆ(์ ๋ ฌ, MST)
1. ๋ชจ๋ ํ์ฑ๋ค์ x์ขํ, y์ขํ, z์ขํ๋ฅผ ๊บผ๋ด ๋ฐ๋ก ์ ์ฅํ๊ณ , ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ
2. ์ ๋ ฌํ ๊ฒ์์ ์ธ์ ํ ๊ฒ๋ผ๋ฆฌ ๋น์ฉ์ ๊ณ์ฐ, (์ธ์ ํ ์ ๋๊ฐ + ๋น์ฉ)์ ๊ตฌ์กฐ์ฒด๋ก n-1๊ฐ์ ์์๋ฅผ ๊ฐ์ง๋ ๋ฐฐ์ด 3๊ฐ๋ฅผ ์ ์ธํ๊ณ ์ง์ด๋ฃ์
3. ๊ทธ ๊ตฌ์กฐ์ฒด๋ฐฐ์ด 3๊ฐ๋ ๋น์ฉ์ ๊ธฐ์ค์ผ๋ก ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ
4. ๊ตฌ์กฐ์ฒด ๋ฐฐ์ด 3๊ฐ๋ฅผ ๊ฐ๋ฆฌํค๋ 3๊ฐ์ ์ธ๋ฑ์ค ๋ณ์ xi, yi, zi๋ฅผ ์ ์ธ
5. xi, yi, zi ์ค ์ต์ ๋น์ฉ์ unionFind ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์ฌ์ดํด์ด ํ์ฑ๋๋์ง ํ์ธํ๋ฉด์ ์ง์ด๋ฃ์. ๋ฃ์ผ๋ฉด edge 1์ฆ๊ฐ, ๋ฃ์ด๋ ์๋ฃ์ด๋ xi, yi, zi๋ ์ต์์ผ์ 1 ์ฆ๊ฐ์ํจ๋ค
6. edge๊ฐ n-1๊ฐ๊ฐ ๋๋ฉด ์ ์ง -> ์ด value ์ถ๋ ฅ
ํผ๊ณผ์
1. MST๋ก ํ์ด์ผํ๋ ๋ฌธ์ ์ธ๊ฑด ๋ฐ๋ก ์. ๊ทผ๋ฐ ๊ฐ์ ์ด ์ฃผ์ด์ง์ง ์์ -> ๊ฐ์ ์ ์ง์ ๋ง๋ค์ด์ผํจ
2. ๋ชจ๋ ํ์ฑ๊ฐ์ ๋น์ฉ์ ๊ตฌํ๋๊ฑด ๋๋ฌด ์ค๋๊ฑธ๋ฆฌ๊ณ , ๋ฉ๋ชจ๋ฆฌ ์๋ชจ๊ฐ ์ฌํจ
-> ๊ฐ์ฅ ๊ฐ๊น์ด ๊ฒ์ด ๋ ๋งํ ๊ฒ๋ค๋ผ๋ฆฌ๋ง ๋น๊ตํ์ฌ ๊ฐ์ ์ ๋ง๋ค์
3. ๋ชจ๋ ํ์ฑ์ ์ ๋ ฌํ์ฌ ์ธ์ ํ ๊ฒ๋ผ๋ฆฌ ํ ๊น?
-> ์ด๋ค ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ ๊ฒ์ธ์ง ๋ฌธ์ ๊ณ , ๋ ์ ๋ ฌํ๋๋ผ๋ ์ธ์ ํ์ง๋ง ๊ฑฐ๋ฆฌ๋ ์ ์ผ ๋ฉ ์ ์์ -> ๋น์ฉ๊ณ์ฐ๊ณต์์ด ์ขํ๋ณ๋ก ๋
๋ฆฝ์ ์ด๊ธฐ์
4. ๊ทธ๋ผ ์ขํ๋ณ๋ก ๋ชจ๋ ์ ๋ค์ ์ ๋ ฌํ์ฌ ์ธ์ ํ ๊ฒ๋ผ๋ฆฌ ๋น์ฉ์ ๊ณ์ฐํ๊ณ , ๋ ๊ทธ ๋น์ฉ์ ์ ๋ ฌํ๋ฉด ๋๊ฒ ๊ตฌ๋
-> ๊ทธ๋ผ ๋น์ฉ, ๋ ์ธ์ ํ ์ขํ๋ฅผ ๊ฐ์ง๊ณ ์๋ ๊ตฌ์กฐ์ฒด๋ฅผ ์ ์ธํ๋๊ฒ ์ข๊ฒ ๊ตฌ๋
5. ์ด๋ ๊ฒ ๊ฐ์ ์ ์ป๊ณ , ํ๋์ฉ ์ง์ด๋ฃ๋๋ฐ ์ด edge๋ N-1๊ฐ๋๊น ๋ฃ์ ๋๋ง๋ค edge๋ฅผ 1๊ฐ์ฉ ์ฆ๊ฐ์์ผ n-1์ด ๋๋ฉด ์ ์ง์ํค๋ฉด ๋๊ฒ ๊ตฌ๋
6. ํต๊ณผ
์ฝ๋
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAX_PLANET 100000
using namespace std;
typedef struct Planet {
int x;
int y;
int z;
} Planet;
typedef struct Distance {
int first;
int second;
int distance;
bool operator < (Distance d) {
return distance < d.distance;
}
} Distance;
Planet planet[MAX_PLANET];
Distance xyz[3][MAX_PLANET];
int numOfPlanet, checkPlanet[MAX_PLANET], tempXYZ[MAX_PLANET];
vector<vector<int>> set;
int abs(int a) {
return a < 0 ? (-1) * a : a;
}
long long getMinValue();
bool putSet(int a, int b);
bool compX(int a, int b) {
return planet[a].x < planet[b].x;
}
bool compY(int a, int b) {
return planet[a].y < planet[b].y;
}
bool compZ(int a, int b) {
return planet[a].z < planet[b].z;
}
void initAndSortXYZ();
int main() {
cin >> numOfPlanet;
for (int i = 0; i < numOfPlanet; i++)
cin >> planet[i].x >> planet[i].y >> planet[i].z;
for (int i = 0; i < MAX_PLANET; i++)
checkPlanet[i] = -1;
cout << getMinValue();
}
long long getMinValue() {
long long value = 0;
int Xi = 0, Yi = 0, Zi = 0, edge = 0;
initAndSortXYZ();
while (edge < numOfPlanet - 1) {
int xd = xyz[0][Xi].distance, yd = xyz[1][Yi].distance, zd = xyz[2][Zi].distance;
if (xd <= yd && xd <= zd) {
if (putSet(xyz[0][Xi].first, xyz[0][Xi].second)) {
value += xd;
edge++;
}
Xi++;
}
else if (yd <= xd && yd <= zd) {
if (putSet(xyz[1][Yi].first, xyz[1][Yi].second)) {
value += yd;
edge++;
}
Yi++;
}
else {
if (putSet(xyz[2][Zi].first, xyz[2][Zi].second)) {
value += zd;
edge++;
}
Zi++;
}
}
return value;
}
void initAndSortXYZ() {
cout << endl;
for (int k = 0; k < 3; k++) {
for (int i = 0; i < numOfPlanet; i++)
tempXYZ[i] = i;
if(k == 0) sort(tempXYZ, tempXYZ + numOfPlanet, compX);
else if(k==1) sort(tempXYZ, tempXYZ + numOfPlanet, compY);
else if(k==2) sort(tempXYZ, tempXYZ + numOfPlanet, compZ);
for (int i = 0; i < numOfPlanet - 1; i++) {
xyz[k][i].first = tempXYZ[i];
xyz[k][i].second = tempXYZ[i + 1];
if (k == 0)
xyz[k][i].distance = abs(planet[tempXYZ[i]].x - planet[tempXYZ[i + 1]].x);
else if (k == 1)
xyz[k][i].distance = abs(planet[tempXYZ[i]].y - planet[tempXYZ[i + 1]].y);
else if (k == 2)
xyz[k][i].distance = abs(planet[tempXYZ[i]].z - planet[tempXYZ[i + 1]].z);
}
for (int i = 0; i < numOfPlanet - 1; i++)
cout << "( " << xyz[k][i].first << ", " << xyz[k][i].second << ", " << xyz[k][i].distance << ") ";
sort(xyz[k], xyz[k] + numOfPlanet -1);
for (int i = 0; i < numOfPlanet - 1; i++)
cout << "( " << xyz[k][i].first << ", " << xyz[k][i].second << ", " << xyz[k][i].distance << ") ";
cout << endl;
}
cout << endl;
}
bool putSet(int a, int b) {
if (checkPlanet[a] == -1 && checkPlanet[b] == -1) {
vector<int> temp;
temp.push_back(a);
temp.push_back(b);
set.push_back(temp);
checkPlanet[a] = set.size() - 1;
checkPlanet[b] = set.size() - 1;
}
else if (checkPlanet[a] == -1) {
checkPlanet[a] = checkPlanet[b];
set[checkPlanet[b]].push_back(a);
}
else if (checkPlanet[b] == -1) {
checkPlanet[b] = checkPlanet[a];
set[checkPlanet[a]].push_back(b);
}
else if (checkPlanet[a] < checkPlanet[b]) {
int temp = checkPlanet[b];
for (int i = 0; i < set[temp].size(); i++) {
checkPlanet[set[temp][i]] = checkPlanet[a];
set[checkPlanet[a]].push_back(set[temp][i]);
}
set[temp].clear();
}
else if (checkPlanet[a] > checkPlanet[b]) {
int temp = checkPlanet[a];
for (int i = 0; i < set[temp].size(); i++) {
checkPlanet[set[temp][i]] = checkPlanet[b];
set[checkPlanet[b]].push_back(set[temp][i]);
}
set[temp].clear();
}
else
return false;
return true;
}