c언어 2406번 안정적인 네트워크 (백준)

#include <stdio.h>
#include <stdlib.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;
}

int main(void)
{
	int n, m, i, j, gap, cnt = 0;
	scanf("%d %d", &n, &m);
	Node *g = (Node*) malloc(sizeof(Node) * (n*(n-1))); //크기가 크다면 동적할당이 더욱 빠릅니다.
    Node key;
	int p[1001]; //노드가 속한 부분집합의 대표노드를 저장
	
	for(i=1; i<=n; i++) p[i] = i;
	for(i=0; i<m; i++) { //연결되어있는 것 입력
		int a, b;
		scanf("%d %d", &a, &b);
		merge(p, a, b);
	}
	
	for(i=1; i<=n; i++) {       //컴퓨터들을 이을때의 비용을 입력받음 (간선 만들기)
		for(j=1; j<=n; j++) {
			 int tmp = 0;
			 scanf("%d", &tmp);
			 if(tmp && i!=1 && j!=1) { //(단 컴퓨터 1일땐 간선을 만들지 않는다)
			 	g[cnt].x = i;
			 	g[cnt].y = j;
			 	g[cnt++].v = tmp;
			 }
		}
	}
	
	gap = cnt/2;        //shell sort
	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;
	}
	
	int mst=0, mstCnt = 0;
	Node must[1000];
	for(i=0; i<cnt; i++) {           //krustal 알고리즘
		if(find(p, g[i].x) != find(p, g[i].y)) {
			mst += g[i].v;
			must[mstCnt++] = g[i]; //연결해야 할 간선을 따로 저장
			merge(p, g[i].x, g[i].y);
		}
	}
	
	printf("%d %d\n", mst, mstCnt);   //mst의 가중치의 합과, 연결해야할 간선
	
	for(i=0; i<mstCnt; i++) { //연결해야할 간선들을 출력
		printf("%d %d\n", must[i].x, must[i].y);
	}
}

 

풀이 : krustal 알고리즘

 

문제에서 모든 컴퓨터는 1번째 컴퓨터하고만 연결이 되어있다가, 1번째 컴퓨터가 부서져서

2~n번째 컴퓨터 모두 서로서로 연결되어 있지 않은 상황입니다.

 

문제에선 2~n번째 컴퓨터를 이을 mst을 구하라고 하며,

 

m개의 공짜로 이어주는 것과

 

행렬로 가중치가 있는 간선들을 줍니다.

 

입력 받은 간선들을 이용하여 krustal알고리즘으로 mst을 구하고, 이 mst을 이루기 위한 간선들을 출력하면됩니다.

 

1. n, m입력

2. m개의 정보를 입력받고, 입력받은 컴퓨터끼리 연결해 줍니다. (union-find)

3. 간선들의 정보를 입력받고 구조체에 대입합니다 (단 첫번째 컴퓨터가 있는 간선은 대입하지 않습니다)

4. 가중치를 기준으로 오름차순 정렬합니다.

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

6. mst의 가중치, 연결할 간선의 개수를 출력합니다.

7. mst을 만들때 필요한 간선들을 출력합니다.

 

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

2406번: 안정적인 네트워크