[백준/C++] 1043번: 거짓말

문제

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

---

문제 요약

지민이는 각 파티에서 거짓말을 하고 싶어한다.

 

하지만, 몇몇 사람들은 이미 이야기의 진실을 알고 있다.

 

따라서, 이런 사람들이 파티에 왔을 경우, 지민이는 진실을 이야기할 수 밖에 없다.

 

당연히 어떤 사람이 다른 파티에서 진실을 듣고, 또다른 파티에서는 거짓말을 들었을 경우가 없도록 피해야 한다.

 

거짓말을 할 수 있는 파티 수의 최대를 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// uf[i]: i번 사람의 그룹 번호
int uf[55];

// t_uf[i]: i번 그룹이 진실을 아는지 여부
bool t_uf[55];

// 파티 정보 저장
vector<int> party[55];

// 진실을 알고 있는 사람 리스트
vector<int> t_person;

// x번 사람의 그룹 번호 탐색 (그룹 대표 번호)
int find(int x) {
	if (uf[x] == x) {
		return x;
	}

	uf[x] = find(uf[x]);
	return uf[x];
}

// x번 사람과 y번 사람의 그룹 병합
void union_(int x, int y) {
	x = find(x);
	y = find(y);

	uf[x] = y;
}

int main() {
	// 입출력 시간 단축
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 사람 수, 파티 수
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		uf[i] = i;
	}

	// 진실을 알고 있는 사람 수
	int t;
	cin >> t;

	for (int i = 0; i < t; i++) {
		int num;
		cin >> num;
		t_person.push_back(num);
	}

	// 파티 정보 입력
	for (int i = 0; i < m; i++) {
		int cnt;
		cin >> cnt;

		vector<int> tmp(cnt);

		for (int j = 0; j < cnt; j++) {
			cin >> tmp[j];
		}

		// 같은 파티에 참여한 사람들의 그룹 병합
		for (int j = 1; j < cnt; j++) {
			union_(tmp[0], tmp[j]);
		}

		party[i] = tmp;
	}

	// 진실을 아는 사람이 속한 그룹을 체크
	for (int p : t_person) {
		int root = find(p);
		t_uf[root] = true;
	}

	// 파티별로 거짓말이 가능한지 체크
	int answer = 0;
	for (int i = 0; i < m; i++) {
		// 기본적으로 거짓말 가능하다고 가정
		bool canLie = true; 

		// 파티 참석 인원 중, 진실을 알고 있는 사람이 속한 그룹의 사람이라면 거짓말 불가
		for (int person : party[i]) {
			if (t_uf[find(person)]) {
				canLie = false;
				break;
			}
		}
		
		if (canLie) answer++;
	}

	cout << answer;

	return 0;
}

---

코드 설명

그룹을 관리해야 하므로, Union-Find 분리 집합을 이용하여 문제를 해결한다.

 

1. 진실을 알고 있는 사람 정보를 벡터에 저장한다.

 

2. 각 파티에 참여하는 사람의 정보를 입력 받고, 같은 파티에 참여한 사람들의 그룹을 병합한다.

 

3. 각 그룹 내 진실을 알고 있는 사람이 존재하는지 체크한다. (그룹 체크)

 

4. 각 파티 내 진실을 알고 있는 그룹에 속한 사람이 존재하는지 체크한다. (파티 체크)