c언어 2887번 행성 터널 (백준)

#include <stdio.h>

//한점에서 가장 가까운점끼리 연결하는 것이 최소 스패닝 트리를 만들 수 있습니다
//한점은 x축을 기준으로 2곳, y축을 기준으로 2곳, z축을 기준으로 2곳의 가까운 점이 있다고 볼 수 있으며,
//위의 모든 경우를 하나의 간선들로 만든다음, 간선들을 가중치 값으로 오름차순하여 정렬합니다
//정렬한 간선들로 최소 스패닝 트리를 위해, Krustal 알고리즘을 사용합니다.

typedef struct Node {
	int x;
	int y;
	int z;
	int num;
}Node;

int ab(int x) {
	if(x<0) return -1*x;
	return x;
}

int min(int x, int y) {
	return x = (x<y) ? x : y;
}

void shellX(Node in[], int n) {
	int i,j, gap = n/2;
	Node key;
	while(1) {
		if(gap%2 == 0) gap++;
		for(i = gap; i<n; i++) {
			key = in[i];
			for(j=i-gap; j>=0; j-=gap) {
				if(key.x < in[j].x) in[j+gap] = in[j];
				else break;
			}
			in[j+gap] = key;
		}
		if(gap==1) break;
		gap>>=1;
	}
} 

void shellY(Node in[], int n) {
	int i,j, gap = n/2;
	Node key;
	while(1) {
		if(gap%2 == 0) gap++;
		for(i = gap; i<n; i++) {
			key = in[i];
			for(j=i-gap; j>=0; j-=gap) {
				if(key.y < in[j].y) in[j+gap] = in[j];
				else break;
			}
			in[j+gap] = key;
		}
		if(gap==1) break;
		gap>>=1;
	}
} 

void shellZ(Node in[], int n) {
	int i,j, gap = n/2;
	Node key;
	while(1) {
		if(gap%2 == 0) gap++;
		for(i = gap; i<n; i++) {
			key = in[i];
			for(j=i-gap; j>=0; j-=gap) {
				if(key.z < in[j].z) in[j+gap] = in[j];
				else break;
			}
			in[j+gap] = key;
		}
		if(gap==1) break;
		gap>>=1;
	}
} 

int find(int p[], int x) {
	if(x == p[x]) return x;
	return p[x] = find(p, p[x]);
}

void merge(int p[], int x, int y) {
	x = find(p, x);
	y = find(p, y);
	if(x!=y) p[x] = y;	
}

int main(void)
{
	int n, value=0;
	scanf("%d", &n);
	Node in[n];
	Node v[n*3]; 
	int p[n];
	for(int i=0; i<n; i++) p[i] = i;
	
	for(int i=0; i<n; i++) { //행성 위치 입력 
		scanf("%d %d %d", &in[i].x, &in[i].y, &in[i].z);
		in[i].num = i;
	}
	
	shellX(in, n); //x좌표로 오름차순으로 쉘 정렬
	for(int i=0; i<n-1; i++) { 
		v[i].x = in[i].num;
		v[i].y = in[i+1].num;
		v[i].z = min(ab(in[i].x-in[i+1].x), min(ab(in[i].y-in[i+1].y), ab(in[i].z-in[i+1].z)));
	}
	
	value += n-1;
	
	shellY(in, n); //y좌표로 오름차순으로 쉘 정렬
	for(int i=0; i<n-1; i++) {
		v[i+value].x = in[i].num;
		v[i+value].y = in[i+1].num;
		v[i+value].z = min(ab(in[i].x-in[i+1].x), min(ab(in[i].y-in[i+1].y), ab(in[i].z-in[i+1].z)));
	}
	
	value += n-1;
	shellZ(in, n); //z좌표로 오름차순으로 쉘 정렬
	for(int i=0; i<n-1; i++) {
		v[i+value].x = in[i].num;
		v[i+value].y = in[i+1].num;
		v[i+value].z = min(ab(in[i].x-in[i+1].x), min(ab(in[i].y-in[i+1].y), ab(in[i].z-in[i+1].z)));
	}
	
	shellZ(v, (n-1)*3); //가중치로 오름차순으로 쉘 정렬
	
	int max = 3*n-3;
	int sum = 0;
	
	for(int i=0; i<max; i++) {
		if(find(p, v[i].x) != find(p, v[i].y)) {
			sum += v[i].z;
			merge(p, v[i].x, v[i].y);
		}
	}
	
	printf("%d", sum);
}

 

풀이 : Krustal 알고리즘, 정렬

 

행성들의간의 최소 스패닝 트리를 만들어야 합니다.

한 행성은 x축, y축, z축을 기준으로 보면 가까운 행성들이 각각 2개씩 총6개가 있음을 알 수 있습니다. (물론 끝자락에 있지 않은 행성을 의미합니다)

 

즉 행성들을 x축으로 정렬 한다음, 인접한 것끼리 가중치를 구한 다음 간선을 만들어주고

또 행성들을 y축으로 정렬 한다음, 인접한 것끼리 가중치를 구한 다음 간선을 만들어주고

또 행성들을 z축으로 정렬 한다음, 인접한 것끼리 가중치를 구한 다음 간선을 만들어 줍니다.

 

(어느 축에서도 서로 가깝지 않은 두 행성들을 묶은 간선은 만들 이유가 없습니다.)

 

 

 

이렇게 인접한 점들끼리의 간선들을 한번에, 가중치를 기준으로 오름차순으로 또 한번 정렬해줍니다.

 

이 다음 Krustal 알고리즘을 사용하면, 각 행성들을 최소 가중치로 이어줄 MST를 구할 수 있습니다.

 

 

 

1. 구조체로 좌표 x, y, z 그리고 그 좌표가 몇번째로 입력받았는지를 담는 num 을 만듭니다.

2. 좌표를 입력받습니다.

3. 입력받은 좌표들을 x축으로 정렬 합니다.

4. 인접했있는 점들의 가중치를 구한 다음 그 좌표들의 num을 이용하여, 간선들을 저장하는 구조체 변수에 저장합니다.

5. 입력받은 좌표들을 y축으로 정렬 합니다.

6. 인접했있는 점들의 가중치를 구한 다음 그 좌표들의 num을 이용하여, 간선들을 저장하는 구조체 변수에 저장합니다.

7. 입력받은 좌표들을 z축으로 정렬 합니다.

8. 인접했있는 점들의 가중치를 구한 다음 그 좌표들의 num을 이용하여, 간선들을 저장하는 구조체 변수에 저장합니다.

9. 만들어낸 간선들을 Krustal 알고리즘을 위해, 가중치를 기준으로 오름차순 정렬을 합니다.

10. union-find을 이용하여, 두 개의 행성이 같은 집합에 있지 않으면, 가중치를 sum에 누적한다음 두 행성이 속한 부분집합들을 합칩니다.

11. sum을 출력합니다.

 

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

2887번: 행성 터널