골드4 - 백준 1043 거짓말

백준 1043 거짓말

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

접근방법

우선 진실을 아는 사람들이 포함되어 있는 파티의 사람들은 전부 진실을 아는 사람이 된다. 따라서 진실을 아는 사람들을 전부 체크하고 한명이라도 포함되어 있는 파티가 있다면 제외시켜주고, 이후 남은 파티의 수를 출력하면 된다.

풀이

진실을 아는 사람들을 known queue에 추가해주었다. 그리고 known에 있는 사람들을 한명씩 꺼내주어 각 파티에 그 사람이 포함되어 있는지 검사해준다. 만약 포함되어 있다면, 해당 파티에 참여한 사람들을 전부 확인해서 known queue에 넣어주는데 check배열을 통해 이미 진실을 알고있다고 확인이 된 사람이면 중복하여 queue에 넣지 않는다. 또한, 해당 파티를 check_party배열에 체크해주어 제거해준다. known queue에 다음 사람을 확인할 때도 이미 제거된 파티는 확인해 줄 필요가 없기 때문에 continue로 건너뛰어준다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool checked[51];
bool checked_party[50];
vector<vector<int>> party;

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

	int N, M;
	cin >> N >> M;

	int k;
	cin >> k;

	queue<int> known;

	for (int i = 0; i < k; i++)
	{
		int temp;
		cin >> temp;
		known.push(temp);
	}

	for (int i = 0; i < M; i++)
	{
		vector<int> t;
		party.push_back(t);

		int p;
		cin >> p;
		for (int j = 0; j < p; j++)
		{
			int temp;
			cin >> temp;
			party[i].push_back(temp);
		}
	}

	while (!known.empty())
	{
		int person = known.front();
		known.pop();

		for (int i = 0; i < M; i++)
		{
			if (checked_party[i])
				continue;

			for (int j = 0; j < party[i].size(); j++)
			{
				if (party[i][j] == person)
				{
					checked_party[i] = true;

					for (int l = 0; l < party[i].size(); l++)
					{
						if (checked[party[i][l]])
							continue;
						known.push(party[i][l]);
					}
					break;
				}
			}
		}
	}

	int answer = 0;

	for (int i = 0; i < M; i++)
	{
		if (!checked_party[i])
			answer++;
	}

	cout << answer << '\n';

	return 0;
}