문제

https://www.acmicpc.net/problem/1043
보통은 유니온파인드 집합 이런 식으로 푸는 것 같다.
그런데 나는 조금 다르게 풀었다.

풀이

Aha! (핵심)

• 진실을 아는/들은 사람과 같은 파티에 참석한 사람 --> 모두 진실만을 들어야 한다.

풀이방법

• 진실을 아는/들은 사람과 같은 파티에 참석한 사람 --> 모두 진실만을 들어야 한다.

  • bool타입 배열 people로 표시

• 파티 참가자의 people 값이 모두 false이면 --> 그 파티에선 과장을 말해도 된다.

  • bool타입 배열 party로 표시

• 배열 party를 순회하며, 값이 false(과장을 말해도 되는 경우)인 개수를 세어준다.

어려웠던 점

• i = -1; // 그러므로 첫번째 파티부터 다시 반복문 돌기.
  처음에 이 부분을 놓쳤었다.
  반례 : https://gusdnr69.tistory.com/114 여기 참고.

코드

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

using namespace std;

int main() {
	/*input*/
	int N, M; cin >> N >> M; //사람의 수, 파티의 수
	bool people[51] = { false }; //각 사람이 진실을 아는지
	bool party[51] = { false }; //각 파티에서 진실을 말해야 하는지
	vector<vector<int>> member(M); //각 파티에 누가 오는지

	int T; cin >> T; //진실을 아는 사람 수
	while(T--) {
		int input; cin >> input;
		people[input] = true;
	}

	for (int i = 0; i < M; i++) {
		int m; cin >> m; //i번째 파티에 오는 사람 수
		while(m--) {
			int input; cin >> input;
			member[i].push_back(input);
		}
	}


	/*solve*/
	for (int i = 0; i < M; i++) {
		bool isThereTruth = false; //진실을 아는 사람이 파티에 오는지
		for (int j = 0; j < member[i].size(); j++) {
			if (people[member[i][j]]) {
				isThereTruth = true;
				party[i] = true;
				break;
			}
		}

		if (!isThereTruth) { continue; } //안 온다면 상관없고,

		for (int j = 0; j < member[i].size(); j++) { //온다면
			if (people[member[i][j]] == false) {
				people[member[i][j]] = true; //그 파티의 모든 참석자는 지민이한테 진실을 듣게 됨.
				//근데 이번에 true로 바꿔준 사람들은, 여태까지는 배열 값이 false여서 넘어갔었음.
				i = -1; // 그러므로 첫번째 파티부터 다시 반복문 돌기.
			}
		}
	}


	int cnt = 0;
	for (int i = 0; i < M; i++) {
		if (!party[i])
			cnt++;
	}
	cout << cnt;


	return 0;
}