c언어 6091번 핑크 플로이드 (백준)

#include <stdio.h>

typedef struct Node{int x, y, 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; //p[y]=x도 상관없습니다.
}

void sort(int arr[1024], int cnt) { //shell sort 
	int i, j, key, gap = cnt/2;
	while(1) {
		if(gap%2==0) gap++;
		for(i=gap; i<cnt; i++) {
			key = arr[i];
			for(j=i-gap; j>=0; j-=gap) {
				if(key < arr[j]) arr[j+gap] = arr[j];
				else break; 
			}
			arr[j+gap] = key;
		}
		if(gap==1) break;
		gap >>= 1;
	}
}

int main(void) {
	int n, i, j, gap, cnt = 0;
	scanf("%d", &n);
	int p[n+1]; //노드가 속한 부분집합의 대표 노드를 담는
	int arr[n+1][n]; //mst에서 어디와 연결되어있는지를 담는
	Node g[n*(n-1)/2], key; //간선을 담을 배열
	
	for(int i=1; i<=n; i++) { //배열 초기화
		p[i] = i;
		arr[i][n-1] = 0;
	}
	
	for(i = 1; i<n; i++) { //간선을 입력받음
		for(j = i+1; j<=n; j++) {
			g[cnt].x = i;
			g[cnt].y = j;
			scanf("%d", &g[cnt++].v);
		}
	}
	
	gap = n/2;               //간선을 가중치를 기준으로 오름차순 정렬
	while(1) {
		if(gap%2==0) gap++;
		for(i=gap; i<cnt; 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;
	}
	
	for(i=0; i<cnt; i++) { //krustal 알고리즘
		if(find(p, g[i].x) != find(p, g[i].y)) {
			arr[g[i].x][arr[g[i].x][n-1]++] = g[i].y; //어떤 노드와 연결 됬는지를 저장
			arr[g[i].y][arr[g[i].y][n-1]++] = g[i].x;
			merge(p, g[i].x, g[i].y);
		}
	}
	
	for(i=1; i<=n; i++) { //mst을 이루는 노드들을 1번째부터 누구와 연결되었는지를 개수와 연결된 노드들을 오름차순 순서대로 출력
		printf("%d ", arr[i][n-1]);
		sort(arr[i], arr[i][n-1]);
		for(j=0; j<arr[i][n-1]; j++) printf("%d ", arr[i][j]);
		printf("\n");
	}
}

풀이 : krustal 알고리즘

 

1. n을 입력받습니다.

2. 간선들을 입력받습니다.

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

4. krustal 알고리즘으로 mst을 구합니다.

5. mst에서 특정 노드에 연결되어있는 노드들의 개수와, 그 종류를 배열에 저장합니다

6. 1번째 노드부터, mst에서 연결된 노드의 개수와, 연결되어있는 노드들을 번호순(오름차순)으로 출력합니다.

 

 

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

6091번: 핑크 플로이드