c언어 16398번 행성 연결 (백준)

#include <stdio.h>

typedef struct Node{ //간선을 받을 구조체
	int x; 
	int y;
	int v; //가중치
}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;
	scanf("%d", &n);
	int N = n*n;
	Node g[N];
	int p[n];
	
	for(int i=0; i<n; i++) { //간선을 행렬처럼 입력 받습니다.
		p[i] = i;
		for(int j=0; j<n; j++) {
			g[i*n+j].x = i;
			g[i*n+j].y = j;
			scanf("%d", &g[i*n+j].v);
		}
	}
	
	int i, j, gap = N/2;
	Node key;
	
	while(1) { ///shell sort
		if(gap%2==0) gap++;
		for(i=gap; i<N; i++) {
			key = g[i];
			for(j=i-gap; j>=0; j-=gap) {
				if(key.v < g[j].v) g[j+gap] = g[j];
				else break;
			}
			g[j+gap] = key;
		}
		if(gap == 1) break;
		gap >>= 1;
	}
	
	
	long long int ans = 0; //값이 int형 범위를 넘어갈 수 있으니, long long int로
	for(i=0; i<N; i++) { //krustal 알고리즘
		if(find(p, g[i].x) != find(p, g[i].y)) {
			ans += g[i].v;
			merge(p, g[i].x, g[i].y);
		}
	}
	
	printf("%lld", ans);
	
}

풀이 : krustal 알고리즘

 

1. 행렬로 받은 데이터를 , 간선의 정보로 바꿉니다.

2. 간선들을 가중치를 기준으로 오름차순 정렬합니다.

3. Krustal 알고리즘으로 MST을 만듭니다.

4. MST(최소 스패닝 트리)의 총 가중치를 출력합니다. ( long long int 로 적어주어야 합니다)

 

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

16398번: 행성 연결