c언어 1414번 불우이웃돕기 (백준)

#include <stdio.h>
#define M 100

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, N, sum = 0; //sum은 모든 랜선의 길이의 합
	scanf("%d", &n);
	N = n*n;
	int p[n]; //노드가 속한 부분집합의 대표노드 저장
	int root[n]; //i번째가 부분집합의 root인지를 담는 배열
	Node g[N]; //간선을 담을 배열
	
	for(int i=0; i<n; i++) {
		root[i] = 0; //배열 초기화
		p[i] = i; //처음엔 부분집합의 root을 자기자신으로 초기화
		for(int j=0; j<n; j++) { //간선 입력 받기
			int tmp = i*n+j;
			g[tmp].x = i;
			g[tmp].y = j;
			char c = 0;
			scanf(" %c", &c);
			if(c == '0') g[tmp].v = M; //랜선이 없다면, 나중에 MST을 구하기 쉽게 매우 큰 값을 준다.
			else if(c >= 'a') g[tmp].v = c-'a'+1;
			else g[tmp].v = c-'A'+27;
			
			if(c != '0') sum += g[tmp].v; //랜선의 길이가 주어지면, sum에 누적
		}
	}
	
	int i, j, gap = N/2;
	Node key;
	
	while(1) {                          //shell sort
		if(gap%2==0) gap++;
		for(i=gap; i<N; 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; //MST의 랜선의 합                  //Krustal 알고리즘
	for(i=0; i<N; i++) {
		if(find(p, g[i].x) != find(p, g[i].y) && g[i].v < M) {
			mst += g[i].v;
			merge(p, g[i].x, g[i].y);
		}
	}
	
	for(i=0; i<n; i++) root[find(p, i)] = 1;     //부분집합의 대표노드들을 찾기
    
	int cnt = 0;
	for(i=0; i<n; i++) if(root[i]) cnt++;   //부분집합의 개수 찾기
	
	if(cnt>1) printf("-1");  //부분집합이 두 개 이상이면, 사실 MST가 없다는 의미이다.
	else printf("%d", sum-mst); //전체 랜선의 길이의 합 - MST에 속한 랜선의 길이의 합
	return 0;
}

풀이 : Krustal 알고리즘 (최소 스패닝 트리)

 

1. 간선을 입력 받습니다. 문자로 입력받은 것은 문제의 조건에 맞게 숫자로 변환해 줍니다.

1.1) 0을 입력받았을 경우 간선의 가중치를 특정한 값으로 대입해줍니다 (나중에 MST을 구할 때 제외할 수 있습니다)

1.2) 0이 아닐경우의 모든 랜선의 합들을 sum에 누적합니다.

 

2. 입력받은 간선들을 정렬합니다 (퀵 정렬이 더 빠릅니다)

 

3. MST라고 가정하고, 최소 스패닝 트리를 구합니다. (아직 최소스패닝트리를 만들 수 있을지는 모릅니다)

 

4. 부분집합의 개수를 구하기 위해, 부분집합의 대표노드를 찾습니다.

 

5. 부분집합의 대표노드가 2개 이상이면, mst을 만들 수 없다는 의미이므로 -1을

 

6. 부분집합의 대표노드가 1개라면, 위에서 만든 mst는 mst가 맞습니다. 고로 전체 랜선 값(sum)에 mst의 랜선 값을 빼면 기부할 수 있는 랜선의 최대치를 출력 할 수 있습니다.

 

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

1414번: 불우이웃돕기