c언어 1368번 물대기 (백준)

#include <stdio.h>
#include <stdlib.h>

typedef struct Node{int x, y, v}Node; //간선을 담을 구조체

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)
{
	int n, i, j, cnt = 0, mst = 0;
	scanf("%d", &n);
	int p[n+1];
	Node *g = (Node*) malloc(sizeof(Node) * (n*(n+1))); //간선은 n*(n+1)개가 만들어진다.
	
	for(i=0; i<=n; i++) { //0번째의 가상의 노드를 만들어준다.
		p[i] = i;
		for(j=1; j<=n; j++) {
            int tmp;
			scanf("%d", &tmp);
			g[cnt].x = i;
			g[cnt].y = j;
			g[cnt++].v = tmp;
		}
	}
	
	Node key;
	int 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;
	}

	for(i=0; i<cnt; i++) {  //krustal 알고리즘
		if(find(p, g[i].x) != find(p, g[i].y)) {
			mst += g[i].v;
			merge(p, g[i].x, g[i].y);
		}
	}
	
	printf("%d", mst);
}

 

풀이 : krustal 알고리즘, 최소 스패닝 트리

 

우물을 파는 비용과, 밭끼리 이어주는 비용 이렇게 두개가 존재해서, 감이 안잡혔으나,

우물을 판다는 비용을, 새로운 우물을 만든 다음, 그 우물에 연결한 비용으로 바꾸어 줄 수 있다.

 

위는 mst을 구하더라도, 우물을 파는 비용 때문에 제대로 구할 수 없으나,

 

 

 

이렇게 가상의 '우물' 이라는 노드를 만들고

우물을 파는 비용을 이 가상의 '우물'에 연결하는 비용으로 바꾸면 된다!

이러면 MST을 적용하기 쉬워진다.

 

1. n을 입력받는다.

2. 노드가 속한 부분집합의 대표노드와, 간선을 담는 구조체 배열을 만듭니다. (단 가상의 우물과 관련된 공간도 주어야 합니다)

3. 우물을 파는 비용, 밭끼리 연결하는 비용을 전부 간선으로 저장합니다.

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

5. krustal 알고리즘 사용

6. mst의 가중치를 출력합니다.

 

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

1368번: 물대기