c언어 1034번 거짓말 (백준)

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

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; //p[y] = x 도 상관없습니다.
	return;
}

int same(int p[], int x, int y) { //두개의 노드가 같은 부분집합인지를 찾는 함수
	x = find(p, x); 
	y = find(p, y);
	return x==y;
}

int main(void) {
	int n, m, s, tmp, ans=0;
	scanf("%d %d", &n, &m); //n, m입력
	scanf("%d", &s); //s 입력
	
	int *p = (int*) malloc(sizeof(int) * (n+1)); //대표노드를 저장할 공간 동적할당
	
	for(int i=0; i<=n; i++) p[i]=i; //처음엔 각각의 노드의 집합의 대표노드는 자기자신
	int save[m][n+1]; //간선? 파티를 저장할 배열
	
	while(s--) { //나의 진실을 아는 사람들은
		scanf("%d", &tmp);
		merge(p, 0, tmp); //나와 같은 집합에 있는 것과 같다.
	}
	
	for(int i=0; i<m; i++) { //파티 정보 입력 받기
		int a, b=0, j;
		scanf("%d", &a);
		for(j=0; j<a; j++) {
			scanf("%d", &tmp);
			if(b) merge(p, b, tmp); //같은 파티에 있는 사람들은 같은 집합에 있다고 볼 수 있다.
			save[i][j] = tmp; //파티를 배열로 저장
			b=tmp;
		}
		save[i][j] = 0;
	}
	
	for(int i=0; i<m; i++) { //저장했던 파티의 내용을 가지고, 내가 과장을 할 수 있는 파티의 개수를 찾기
		int j = 0;
		while(1) {
			if(save[i][j] == 0) ans++; //파티에 참석한 사람이 나와 같은 집합이 아니라면, 나는 과장을 할 수 있다.
			if(same(p, 0, save[i][j])) break; //만약 나와 같은 집합이라면, 나의 진실을 아므로, 그 파티에선 과장을 할 수 없다.
			j++;
		}
	}
	printf("%d", ans); //과장한 파티의 개수
	return 0;
}

 

 

풀이 : union(합집합) + find(찾기)

 

1. 각 사람들의 부분집합의 대표노드를 자기 자신으로한 배열을 만든다.

 

2. 나를 알고 있는 사람들은 나와 같은 부분집합에 있는 것으로 본다.

 

3. 파티에서 같이 참석한 사람들은 같은 부분집합에 있는 것으로 본다.

만약 A는 날 알고 B는 날 모른다 해도, 나는 B에게만 과장을 할 수 없기때문이다. (A와 B는 같은 파티에 있으니)

또한 만약 이전에 파티는 B만 참석했다고 해도 과장을 할 수가 없게 된다.

왜냐하면, B만 있을 때는 과장 했다가, A B가 있는 파티에서 진실만을 말하게 되면, 결국 B는 내가 전에는 과장을 하였음을 알 수 있기 때문이다. 따라서 파티에 같이 참여하는 사람들은 같은 집합으로 묶어준다.

 

4. 3.의 과정을 하는 동안 입력 받은 파티의 정보를 따른 배열에다가 저장해 둔다.

 

5. 저장한 파티의 정보를 가지고, 파티에 자신과 같은 집합인 사람이 없다면 과장이 가능한 파티이며, 이러한 파티가 몇개인지를 구한다.

 

6. 과장이 가능한 파티의 개수를 출력한다.

 

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

1043번: 거짓말