c언어 10423번 전기가 부족해 (백준)

#include <stdio.h>

typedef struct Node{int x, y, v;}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, k, i, j, gap;
	scanf("%d %d %d", &n, &m, &k);
	
	int p[n+1]; //노드가 속한 부분집합의 대표 노드 저장
	char generator[n+1]; //전기가 흐르는 곳인가?
	Node g[m], key; //간선을 받을 구조체 배열과, 정렬에 쓸 구조체 
	
	
	for(int i=1; i<=n; i++) { //배열 초기화
		p[i] = i; //처음엔 부분집합의 대표노드는 자기자신
		generator[i] = 0;
	}
	
	for(i=0; i<k; i++) { //발전소 입력받기
		int temp;
		scanf("%d", &temp);
		generator[temp] = 1; //전기가 흐른다는 의미
	}
	
	for(i=0; i<m; i++) { //간선 입력받기
		scanf("%d %d %d", &g[i].x, &g[i].y, &g[i].v);
	}
	
	gap = m/2;
	while(1) {                            //shell sort
		if(gap%2 == 0) gap++;
		for(i=gap; i<m; 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 ans = 0;
	for(i = 0; i<m; i++) {               //krustal 알고리즘
		int tmpx = find(p, g[i].x);
		int tmpy = find(p, g[i].y);
		
		if(tmpx != tmpy) { 
			if(generator[tmpx] && generator[tmpy]); //둘다 전기가 흐르고 있다면, 연결하지 않는다.
			else { //그렇지 않다면
				if(generator[tmpx] || generator[tmpy]) generator[tmpx] = generator[tmpy] = 1; //전기가 둘 중 한 곳만 흐른다면, 나머지도 흐름으로 바꾸어준다.
				ans += g[i].v; //가중치 누적
				merge(p, g[i].x, g[i].y); //두 노드의 부분집합 합치기
			}
		}
	}
	
	printf("%d", ans); //MST 가중치의 합 출력
}

풀이 : krustal 알고리즘

자세한 풀이 : mst을 구하되, 만약 간선을 이어줄 두 곳에 이미 전기가 흐르고 있다면, 간선을 잇지 않으며,

전기가 흐르지 않다가 흐르게 되면, 그 연결된 부분만 전기가 흐르는 것이 아니라, 그 연결된 부분이 속한 부분집합에 전기가 흐른다고 보아야 한다.

 

이렇게 있다면 (1, 4는 발전소)

 

krustal 알고리즘에 의해 2-3을 연결한다 (2, 3은 이제 같은 부분집합에 있다)

 

3-4을 연결한다 (3에 전기가 흐르지 않으므로 연결이 가능하다)

또한 3에 전기가 흐르므로, 3이 속한 부분집합에는 모두 전기가 흐른다고 볼 수 있다.

이를 나타내기위해, 3이 속한 부분집합의 대표노드가 전기가 들어오는 것을 코딩으로 구현하면 된다.

 

1과 2는 둘다 전기가 흐르고 있기에 연결 하지 않는다.

 

고로 연결된 가중치의 합은 3이다.

 

 

1. n,m 입력받기

2. 발전소 노드 입력받기

3. 간선 입력받기

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

5. krustal 알고리즘

-두 노드가 같은 집합이라면 다음 간선으로

-다른 집합이나, 둘다 전기가 흐르고 있다면 다음 간선으로

위의 두 조건이 아닐경우

-한 쪽에만 전기가 흐르면, 가중치를 누적하며, 안 흐르는 곳의 부분집합의 대표노드에도 이제 전기가 흐른다고 여긴다.

-또한 두 노드의 부분집합을 합친다.

6. mst의 가중치의 총합을 출력한다.

 

추가 : 위의 예시에서

2-3 을 한 다음 3-4을 할 때

2-3의 부분집합의 대표노드가 3이라면 직접 generator[3] = 1 로 하니 전기가 흐름을 나타낼 수 있으며

대표노드가 2라고 해도, 3의 대표노드는 2이므로 generator[find(p, 3)] = generator[find(2)] = 1이 되니

 

union-find을 이용하면, 순서에 상관없이 확실하게 전기가 흘렀음이 공유됩니다.

 

 

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

10423번: 전기가 부족해