[백준 / BOJ] C++ 1043 거짓말

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

1043번: 거짓말

풀이

과장된 이야기를 할 수 있는 파티의 갯수를 세어줘야한다. 

 

우선 문제에서 주어지는 순으로 정리를 해보자.

• 첫번째 줄에는 N,M으로 사람의 수와 파티의 개수를 입력해준다.
• 두번째 줄에는 진실을 아는 사람의 수와 번호가 주어진다.

진실을 아는사람들을 체크하며, 해당 번호를 진실체크하는 queue에 넣어준다.

• 세번째 줄부터는 파티에 오는 사람의 명수와 번호가 주어진다.
• 입력받은 M만큼 반복하며, 해당 파티에 들어가는 사람의 번호를 추가해준다.

이후 파티의 갯수만큼 반복하며, 해당 파티에 진실을 아는사람이 존재할 경우,  

해당 파티에선 과장된 이야기를 하지 못한다. 그렇기에 queue에 전부 삽입해준다.

 

 

Code ( C++ )

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int N, M;
int t; // 진실 아는 사람의 수
int tn; // 진실아는 사람의 넘버
int p; // 파티 참석하는 사람중 진실을 아는사람
bool _isTrueP[51];
bool _isFalseP[51];
vector<int> party[51];
queue<int> q;

int result;

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

	cin >> N >> M;

	fill(_isTrueP, _isTrueP + 51, false);
	fill(_isFalseP, _isFalseP + 51, false);

	cin >> t;

	// 진실을 아는사람 체크
	for (int i = 0; i < t; i++)
	{
		cin >> tn;
		_isTrueP[tn] = true;
		q.push(tn);
	}

	// 파티 참석하는 사람체크
	for (int i = 1; i <= M; i++)
	{
		cin >> tn;
		for (int j = 0; j < tn; j++)
		{
			cin >> p;
			party[i].push_back(p);
		}
	}

	while (!q.empty())
	{
		p = q.front();
		q.pop();

		for (int i = 1; i <= M; i++)
		{
			if (find(party[i].begin(), party[i].end(), p) != party[i].end())
			{
				_isFalseP[i] = true;

				/* 
				 * 해당파티에 진실을 아는사람이 한명이라도 있는경우, 해당 파티인원들도 진실을 알기에
				 * q에 삽입을해줌
				 */
				if (party[i].size() > 1) 
				{
					for (int j = 0; j < party[i].size(); j++)
					{
						if (!_isTrueP[party[i][j]])
						{
							_isTrueP[party[i][j]] = true;
							q.push(party[i][j]);
						}
					}
				}
			}
		}
	}

	for (int i = 1; i <= M; i++)
		if (!_isFalseP[i]) result++;

	cout << result << endl;
}