[BOJ/C++] 1043 거짓말 : Union-Find

문제

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

풀이

Union-Find 연습하려고 풀어 본 문제인데 처음에는 문제도 잘 이해가 안됐다😅 알고리즘 자체는 간단한데.. 더 연습하자👩🏻‍💻👩🏻‍💻

사람 10명
파티 9개
진실을 아는 사람 수 4명 [1번, 2번, 3번, 4번]
첫 번째 파티 2명 [1번, 5번]
두 번째 파티 2명 [2번, 6번]
세 번째 파티 1명 [7번]
네 번째 파티 1명 [8번]
다섯 번째 파티 2명 [7번, 8번]
여섯 번째 파티 1명 [9번]
일곱 번째 파티 1명 [10번]
여덟 번째 파티 2명 [3번, 10번]
아홉 번째 파티 1명 [4번]

집합으로 묶으면
1-5
2-6
7-8
9
3-10
4
파티에 진실을 아는 [1번, 2번, 3번, 4번]과 집합으로 묶인 [1번, 2번, 3번, 4번, 5번, 6번, 10번]이 포함되어 있으면 진실을 말해서는 안된다.
∴ 3번, 4번, 5번, 6번 파티에서만 진실을 말할 수 있다!

위의 내용을 코드로 작성해보면

• N : 사람의 수
• M : 파티의 수
• a, b : 진실을 아는 사람 수와 파티 참석하는 사람의 수 입력 받을 임시 변수
• truth 배열 : 진실을 아는 사람
• people 2차원 배열 : 파티에 참석하는 사람 정보
• parent 배열 : Union-Find 구현할 때 서로소 집합 찾기 위한 배열

1. 문제에서 주어진 정보 변수에 저장해서 입력 받고, part 배열 초기화

2. 파티 참석하는 사람 정보에 따라 Union

3. check 변수 true로 초기화하고, false 되면 진실을 얘기할 수 없다는 의미이다.
   

3-1. 순서대로 isUnion(a, b) 호출하고, 같은 집합에 있을 경우에는 check 변수 false로 변경해준다.

3-2. ans를 처음에 파티 개수로 초기화하고, check가 false일 때마다 -1 해준다.

코드

#include <iostream>
#include <vector>

using namespace std;

int parent[51];
vector<int> truth;
vector<int> people[51];


int Find(int x) {
	if (parent[x] == x)	return x;
	return parent[x] = Find(parent[x]);
}

void Union(int a, int b) {
	int x = Find(a);
	int y = Find(b);

	if (x < y)	parent[y] = x;
	else {
		parent[x] = y;
	}
}

bool isUnion(int a, int b) {
	int x = Find(a);
	int y = Find(b);
	if (x == y)	return true;
	else {
		return false;
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M, a, b;
	cin >> N >> M;
	cin >> a;
	int ans = M;

	for (int i = 0; i < a; i++) {
		cin >> b;
		truth.push_back(b);
	}

	for (int i = 0; i < M; i++) {
		cin >> a;
		for (int j = 0; j < a; j++) {
			cin >> b;
			people[i].push_back(b);
		}
	}

	//parent 배열 초기화
	for (int i = 1; i <= N; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < M; i++) {
		a = people[i][0];
		for (int j = 1; j < people[i].size(); j++) {
			b = people[i][j];
			Union(a, b);
		}
	}

	for (int i = 0; i < M; i++) {
		bool check = true;
		for (int j = 0; j < people[i].size(); j++) {
			if (!check)	break;
			a = people[i][j];
			
			for (int k = 0; k < truth.size(); k++) {
				b = truth[k];
				if (isUnion(a, b)) {
					check = false;
					break;
				}
			}
		}
		if (!check)	ans--;
	}

	cout << ans;

}