c언어 1647번 도시 분할 계획 (백준)

#include <stdio.h>
#define M 1000001

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[100001];
	for(int i=1; i<100001; i++) p[i] = i;
	
	int ans = 0;
	int last = 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;
			last = node.c;
			merge(p, node.a, node.b);
		}
	}
	
	printf("%d", ans-last); //가장 마지막에 추가된 간선을 빼면, 최소 집이 1개이상인 마을을 두개 만들어 낼 때의 거리의 최솟값을 구할 수 있습니다
}

 

 

풀이 : Krustal 알고리즘을 이용하여 MST(최소 스패닝 트리) 을 만든다음 가장 마지막에 추가된 간선을 빼면 됩니다.

 

https://h202.tistory.com/263

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

위의 문제를 보시면 이해하기 더 쉽습니다.

 

1. 간선들을 우선순위큐로 가중치를 기준으로 오름차순 정렬 합니다 (또는 배열로 받은 다음 정렬해도 됩니다)

2. union-find을 이용하여, 두 노드가 같은 집합에 있지 않으면, 간선을 추가합니다. (가중치를 더해준다)

그 다음 두 노드가 속한 부분집합을 합쳐줍니다. (같은 집합이라면, 한번 더 연결시 사이클이 생성되므로, 간선을 추가해서는 안됩니다)

3. 최소 스패닝 트리를 구했습니다!

4. 두 마을 (최소 1개의 집으로 이루어진)에서 각각의 마을의 집들끼리 연결하는데 드는 최소 비용은, MST에 가장 마지막에 추가한(즉 가중치의 값이 가장 큽니다) 간선의 가중치의 값을 빼줍니다

 

 

MST

 

 

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

1647번: 도시 분할 계획