c언어 1197번 최소 스패닝 트리 (백준)

#include <stdio.h>
#define M 100001

void swap(int *x, int *y) { //swap
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

typedef struct Node { //node 
	int a;
	int b;
	int c;
}Node;

typedef struct PriorityQueue { //우선순위큐   
	Node heap[M]; //a b c
	int cnt;
}PriorityQueue;

void push(PriorityQueue *q, int a, int b, int data) { //우선순위 큐 push 
	q->heap[q->cnt].a = a;
	q->heap[q->cnt].b = b;
	q->heap[q->cnt].c = data;
	
	int child = q->cnt;
	int parent = 0;
	if(child) parent = (child-1)/2;
	
	while(child && q->heap[child].c < q->heap[parent].c) {
		swap(&q->heap[child].a, &q->heap[parent].a);
		swap(&q->heap[child].b, &q->heap[parent].b);
		swap(&q->heap[child].c, &q->heap[parent].c); 
		child = parent;
		parent = (parent-1)/2;
	}
	q->cnt++;
}

Node pop(PriorityQueue *q) { //우선순위 큐 pop
	Node res;
	res.a = q->heap[0].a;
	res.b = q->heap[0].b;
	res.c = q->heap[0].c;
	q->cnt--;
	
	q->heap[0].a = q->heap[q->cnt].a;
	q->heap[0].b = q->heap[q->cnt].b;
	q->heap[0].c = q->heap[q->cnt].c;
	
	int parent = 0, tmp = 0;
	int leftChild = 1;
	int rightChild = 2;
	
	while(leftChild < q->cnt) {
		if(q->heap[tmp].c > q->heap[leftChild].c) tmp = leftChild;
		if(q->heap[tmp].c > q->heap[rightChild].c && rightChild < q->cnt) tmp = rightChild;
		if(parent == tmp) break;
		else {
			swap(&q->heap[parent].a, &q->heap[tmp].a);
			swap(&q->heap[parent].b, &q->heap[tmp].b);
			swap(&q->heap[parent].c, &q->heap[tmp].c); 
			parent = tmp;
			leftChild = parent*2+1;
			rightChild = leftChild+1;
		}
	}
	return res;
}

int isEmpty(PriorityQueue* q) { //큐가 비었는지 
	return q->cnt == 0;
}

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) {
	PriorityQueue queue;
	queue.cnt = 0;
	
	int p[10001];
	for(int i=1; i<10001; i++) p[i] = i;
	
	int ans = 0;
	
	int v, e;
	scanf("%d %d", &v, &e);
	
	while(e--) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		push(&queue, a, b, c);
	}
	
	while(!isEmpty(&queue)) {
		Node node = pop(&queue);
		if(find(p, node.a) != find(p, node.b)) { //두 노드가 같은 집합이 아니라면 
			ans += node.c;
			merge(p, node.a, node.b);
		}
	}
	
	printf("%d", ans);
}

 

사용한 알고리즘, 자료구조 : Kruskal 알고리즘, union-find, 우선순위큐 (또는 정렬)

 

Kruskal 알고리즘

1. 가중치를 기준으로 간선을 오름차순 정렬

2. 순서대로 간선을 선택, 단 사이클을 만들면 안됨

3. 간선 선택시 가중치를 더해줌 (최소 스패닝 트리를 구할 수 있게 됩니다)

 

0. 간선의 정보를 받고, 이를 우선순위 큐에 넣습니다 (물론, 배열에 다 저장한 다음, 정렬을 하는 것이 더욱 빠릅니다)

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

2. Kruskal 알고리즘은 오름차순으로 정렬한다음, 순서대로 간선을 선택하되 사이클을 만드는 간선은 배제한다 (사이클이 생성될지는 union(합집합) - find(찾기)를 이용하여, 같은 부분집합에 있는 지를 찾는다. 같은 집합이면, 또 연결시 사이클이 생김을 알 수 있다)

3. 간선을 선택하면, 그 가중치를 더해줍니다

4. Kruskal 알고리즘을 이용하였으니, 최소 스패닝 트리가 구할 수 있게 됩니다. (모든 간선이 연결되어있는 트리)

 

주의할 점 : 최소 스패닝 트리는 모든 간선이 있는 트리입니다. 그러나 간선을 전부 방문했다고, 반복문을 멈춰버리는 코드를 짜면, 최소 스패닝 트리가 만들어 지지 않을 가능성이 있습니다.

고로 반복문을 돌릴 때 break을 사용해서는 안됩니다.

 

왼쪽의 경우에도 전부 방문했다고 멈춰버리면, 최소 스패닝 트리가 만들어 지지 못한다