c언어 1774번 우주신과의 교감 (백준)

#include <stdio.h>
#include <math.h>

typedef struct Node{ //간선을 받을 구조체
	int x;
	int y;
	double num;	
}Node;

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, m, i, j;
	Node key;
	double sum = 0;
	scanf("%d %d", &n, &m);
	int p[n]; //노드가 속한 부분집합의 대표노드 저장
	Node v[n]; //x좌표, y좌표, 몇번째?
	Node g[(n*(n-1))/2 + m]; //몇번째 우주선, 몇번째 우주선, 우주선 사이의 길이 (간선)
	int cnt = 0;
	
	for(i=0; i<n; i++) { //우주선의 좌표 입력받기
		p[i] = i;
		scanf("%d %d", &v[i].x, &v[i].y);
		v[i].num = i;
	} 

	for(i=0; i<n; i++) { //입력받은 우주선의 모든 간선 구하기
		for(j=i+1; j<n; j++) {
			g[cnt].x = v[i].num;
			g[cnt].y = v[j].num;
			g[cnt].num = sqrt(pow((v[i].x-v[j].x), 2) + pow((v[i].y-v[j].y), 2));
			cnt++;
		}
	}
	
	for(i=0; i<m; i++) { //이미 이어져 있는 간선 입력받기
		int c, d;
		scanf("%d %d", &c, &d);
		g[cnt].x = c-1;
		g[cnt].y = d-1;
		g[cnt].num = 0.0;
		cnt++;
	}
	
	int gap=cnt/2;
	
	
	while(1) {                    //shell sort
		if(gap%2 == 0) gap++;
		for(i=gap; i<cnt; i++) {
			key = g[i];
			for(j=i-gap; j>=0; j-=gap) {
				if(key.num < g[j].num) g[j+gap] = g[j];
				else break;
			}
			g[j+gap] = key;
		}
		if(gap == 1) break;
		gap >>= 1;
	}
	
	for(i=0; i<cnt; i++) { //krustal 알고리즘
		if(find(p, (int)g[i].x) != find(p, (int)g[i].y)) {
			sum += g[i].num;
			merge(p, (int)g[i].x, (int)g[i].y);
		}
	}
	
	printf("%.2f", sum);
}

이 코드는 매우 시간이 느립니다, 더 빠른 코드는 백준에 있습니다.

 

풀이 :  최소 스패닝 트리, krustal 알고리즘

1. n, m을 입력받습니다.

2. n개의 좌표를 입력받습니다.

3. 입력 받은 좌표들의 모든 간선들을 구합니다.

4. 이미 이어져 있는 간선들을 입력받습니다.

5. 간선들을 정렬합니다.

6. krustal 알고리즘으로 최소 스패닝 트리를 구합니다.

7. MST의 가중치의 합을 출력합니다.

 

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

1774번: 우주신과의 교감