[백준 1043] 거짓말

거짓말 [C++]

문제 링크: https://www.acmicpc.net/problem/1043

난이도: 🟡🟡🟡🟡

문제 설명

문제 접근

• Set을 이용한 합집합으로 진실을 아는 사람이 포함되어있는지 확인했다.

1. 진실을 아는 사람들의 번호가 주어지고 각 파티에 참여하는 사람들의 번호가 주어진다.

2. 각 파티를 순회하면서 진실을 아는 사람이 포함되어있다면, 그 파티에 참여한 사람들을 진실을 아는 사람들 목록에 추가한다.

3. 각 파티의 수만큼 다시 한번 파티를 순회하며 진실을 아는 사람이 포함되어있는지 확인하고 업데이트한다.

4. 업데이트가 끝났다면, 마지막으로 파티를 순회하며 진실을 아는 사람이 포함되어있는지 확인하고 포함되어있지 않다면, answer을 증가시킨다.
   
   

제출 코드

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

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

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

	// 진실을 알고있는 사람들
	set<int> known;
	int cnt;

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

	// 파티들
	vector<set<int>> parties;
	for (int i = 0; i < M; i++)
	{
		cin >> cnt;
		set<int> nums;
		bool know = false;
		for (int j = 0; j < cnt; j++)
		{
			int temp;
			cin >> temp;

			nums.insert(temp);
			// 진실을 아는 사람들의 집합에 존재한다면, 그 파티에 참석한 인원 전체를 진실을 알고있는 집합에 추가한다.
			if (count(known.begin(), known.end(), temp) > 0)
				know = true;
		}
		if (know)
			set_union(nums.begin(), nums.end(), known.begin(), known.end(), std::inserter(known, known.begin()));
		
		parties.push_back(nums);
	}
	int answer = 0;
	for(int i = 0; i < M + 1; i++)
	{
		// 파티의 수만큼 반복이 끝나면 알고있는 사람이 없는 파티의 수를 센다.
		if (i == M)
		{
			for (int j = 0; j < M; j++)
			{
				set<int> party = parties[j];
				set<int> temp;
				set_union(party.begin(), party.end(), known.begin(), known.end(), std::inserter(temp, temp.begin()));
				// 교집합이 없는경우
				if (temp.size() == party.size() + known.size())
					answer++;
			}
		}
		else 
		{
			// 파티의 수만큼 반복한다.
			for (int j = 0; j < M; j++)
			{
				set<int> party = parties[j];
				set<int> temp;
				set_union(party.begin(), party.end(), known.begin(), known.end(), std::inserter(temp, temp.begin()));
				// 교집합이 없는경우
				if (temp.size() == party.size() + known.size())
					continue;
				else
					set_union(party.begin(), party.end(), known.begin(), known.end(), std::inserter(known, known.begin()));
			}
		}
	}

	cout << answer;
	return 0;
}

결과