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를 빌드합니다.

'추천 관련글,