c언어 1922번 네트워크 연결 (백준)

#include <stdio.h>

typedef struct Node{ //간선을 담을 구조체
	int x;
	int y;
	int v;
}Node;

void shell(Node v[], int m) { //shell 정렬
	int i, j, gap = m/2;
	Node key;
	
	while(1) {
		if(gap%2 == 0) gap++;
		for(i=gap; i<m; i++) {
			key = v[i];
			for(j=i-gap; j>=0; j-=gap) {
				if(key.v < v[j].v) v[j+gap] = v[j];
				else break;
			}
			v[j+gap] = key;
		}
		if(gap == 1) break;
		gap >>= 1;
	}
}

int find(int p[], int x) { //노드가 속한 부분집합의 대표노드 찾기
	if(p[x] == 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;
	scanf("%d %d", &n, &m);
	int p[n+1];
	Node v[m];
	for(int i=1; i<=n; i++) p[i] = i;
	for(int i=0; i<m; i++) scanf("%d %d %d", &v[i].x, &v[i].y, &v[i].v);
	
	shell(v, m);

	int ans = 0;
	for(int i=0; i<m; i++) { //Krustal 알고리즘
		if(find(p, v[i].x) != find(p, v[i].y)) {
			ans += v[i].v;
			merge(p, v[i].x, v[i].y);
		}
	}
	printf("%d", ans);
}

 풀이 : Krustal 알고리즘

1. 간선의 정보를 담아즐 구조체를 정의합니다.

2. n, m입력받기

3. 부분집합의 대표 노드를 담을 배열을 생성합니다.

4. 2.의 배열을 대표노드를 자신으로 값을 넣어줍니다.

5. 간선 입력받습니다.

6. 간선들을 가중치로 오름차순 정렬을 합니다 (저는 shell 정렬을 했습니다. 퀵정렬이 더 빠를 것입니다)

7. Krustal 알고리즘을 사용합니다

8. 최소 스패닝 트리의 전체 가중치를 출력합니다.

 

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

1922번: 네트워크 연결