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;
}