백준 - 거짓말 (1043) [C++]

이 문제는 구현으로 풀었다. 문제 카테고리를 보면 분리 집합, 그래프 등이 나오는데 입력 크기가 작아 구현으로도 풀렸다.

 

이 문제의 핵심은 진실을 아는 사람이 한명이라도 있는 파티에서는 진실을 말할 수 밖에 없고, 그 파티에 참가한 모든 사람이 진실을 알게 된다는 것이다.

 

그러나 위의 핵심을 가지고 풀어도 정답이 나오지 않을 때가 있는데, 이는 진실을 알고 있는 사람이 입력 마지막에 전부 몰려있는 경우이다. 이 경우 파생되는 인원들을 제대로 체크하지 않고 넘어갈 수 있기 때문이다.

 

그래서 진실을 알고 있는 사람들을 마킹하는 함수를 M번 반복하여 정답을 찾을 수 있었다. 만약 파티가 10개이고, 맨 마지막에만 진실을 알고 있는 사람이 있는 파티가 존재한다고 가정하면 최악의 경우 각 루프마다 한명씩 추가가 되기 때문에 최대 M번을 반복하여 확실하게 검증할 수 있다.

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

using namespace std;

#define MAX 50

int N, M;
int knowTruthCount;
bool knowTruth[MAX + 1];
vector<int> party[MAX];

bool isBaseCase() {
	if (knowTruthCount == 0) {
		cout << M << '\n';

		return true;
	}

	return false;
}

void input() {
	cin >> N >> M;
	cin >> knowTruthCount;

	for (int i = 0; i < knowTruthCount; i++) {
		int num;
		cin >> num;

		knowTruth[num] = true;
	}

	for (int i = 0; i < M; i++) {
		int cnt;
		cin >> cnt;

		for (int j = 0; j < cnt; j++) {
			int num;
			cin >> num;

			party[i].push_back(num);
		}
	}
}

bool isContainsTruth(const vector<int>& tempParty) {
	for (int num : tempParty) {
		if (knowTruth[num]) {
			return true;
		}
	}

	return false;
}

void makeAllTruth(const vector<int>& tempParty) {
	for (int num : tempParty) {
		knowTruth[num] = true;
	}
}

void allPossibleTruth() {
	for (int i = 0; i < M; i++) {
		const vector<int> presentParty = party[i];

		if (isContainsTruth(presentParty)) {
			makeAllTruth(presentParty);
		}
	}
}

int solve() {
	for (int i = 0; i < M; i++) {
		allPossibleTruth();
	}

	int result = 0;
	for (int i = 0; i < M; i++) {
		vector<int> presentParty = party[i];

		if (!isContainsTruth(presentParty)) {
			result++;
		}
	}

	return result;
}

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

	input();

	if (isBaseCase()) {
		return 0;
	}

	cout << solve() << '\n';
	
	return 0;
}