c언어 14621번 나만 안되는 연애 (백준)

#include <stdio.h>

typedef struct Node{int u, v, d}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, treeCnt = 0;
	scanf("%d %d", &n, &m);
	int p[n+1]; //노드가 속한 부분집합의 대표 노드 저장
	char isTree[n+1]; //부분집합의 대표노드인가?
	char gender[n+1]; //노드의 성별
	Node g[m]; //간선을 담을 구조체 배열
	Node key;
	
	for(i=1; i<=n; i++) { //성별
		scanf(" %c", &gender[i]);
		p[i] = i;
		isTree[i] = 0;
	}
	
	for(i=0; i<m; i++) { //간선
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		if(gender[x] != gender[y]) { //다른 성별이면 간선 생성
			g[cnt].u = x;
			g[cnt].v = y;
			g[cnt].d = z;
			cnt++;
		}
	}
	
	gap = cnt/2;
	
	while(1) {              //shell sort
		if(gap%2==0) gap++;
		for(i=gap; i<cnt; i++) {
			key = g[i];
			for(j=i-gap; j>=0; j-=gap) {
				if(key.d < g[j].d) g[j+gap] = g[j];
				else break;
			}
			g[j+gap] = key;
		}
		if(gap == 1) break;
		gap >>= 1;
	}
	
	int ans = 0;             //mst의 가중치 총합
	for(int i=0; i<cnt; i++) { //krustal 알고리즘, 단 아직 mst을 만들 수 있을 지는 모른다.
		if(find(p, g[i].u) != find(p, g[i].v)) {
			ans += g[i].d;
			merge(p, g[i].u, g[i].v);
		}
	}
	
	//부분집합의 개수 찾기
	for(int i=1; i<=n; i++) isTree[find(p, i)] = 1; 
	for(int i=1; i<=n; i++) if(isTree[i]) { 
		treeCnt++;
		if(treeCnt>1) break;
	}
	
	if(treeCnt > 1) printf("-1"); //부분집합이 2개 이상이면, mst가 불가하다!
	else printf("%d", ans); //mst가 존재하며, 이 때의 가중치의 총합을 출력하면 된다.
	return 0;
}

풀이 : Krustal 알고리즘, union-find

 

1. n, m입력받습니다.

2. 성별을 입력받습니다.

3. 간선을 입력받습니다. 만약 두 대학이 같은 성별이면, 간성을 생성하지 않습니다.

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

5. mst가 있다고 생각하고 krustal알고리즘으로 mst의 가중치의 합을 구합니다.

6. 부분집합의 개수를 셉니다. 만약 2개이상이라면 mst는 존재하지 않습니다.

7. 부분집합이 2개이상이면 -1을, 1개라면 mst가 있다는 의미이니, mst의 가중치를 출력합니다.

 

https://www.acmicpc.net/submit/14621/58334174

로그인