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

문제

• 1043번 : 거짓말
• Rank : Gold IV
• 링크 : https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

풀이 전략

• 한 파티 안에 진실을 아는 사람이 없다면, 그 파티에서는 거짓말을 할 수 있다.
• 한 파티 안의 멤버 하나라도 진실을 안다면, 그 파티 사람들은 모두 진실을 아는 사람이 된다.
  • 바이러스 전염과 유사.
• 각 파티를 set으로 구성하여, vector에 넣어둔다.
• 진실을 아는 사람을 Queue(Vector로 구현함)에 넣어둔다.
• Queue가 비거나 남은 파티가 없어질때까지, 다음 행동을 반복한다.
  • Queue에서 한 사람을 꺼냄
  • 남은 파티에 해당 인원이 참가한 경우, 다음 행동 수행
    • 해당 파티에 있는 아직 진실을 모르는 사람을 Queue에 집어넣음
    • 해당 파티를 파티 Vector에서 제거
• 루프가 끝난 후, Vector 내에 남은 파티의 수가 정답이다.

 

전체 소스 코드

//Backjoon Problem No.1043
//https://www.acmicpc.net/problem/1043
//Mist16, 2022-03-01
#include <iostream>
#include <vector>
#include <set>

using namespace std;

int M = 0, N = 0;

int isAffected[51] = { 0, };

vector<set<int>> vParty;
vector<int> vAffected;

int main()
{
	int numb, temp;
	//입출력 속도 증가
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> numb;
	//진실을 아는 사람
	for (int i = 0; i < numb; i++)
	{
		cin >> temp;
		vAffected.push_back(temp);
		isAffected[temp] = 1;
	}
	//파티 입력
	for (int i = 0; i < M; i++)
	{
		set<int> cParty;

		cin >> numb;
		for (int j = 0; j < numb; j++)
		{
			cin >> temp;
			cParty.insert(temp);
		}
		vParty.push_back(cParty);
	}

	while (!vAffected.empty() && !vParty.empty())
	{
		int aPerson = vAffected.back();

		vAffected.pop_back();

		for (auto iter = vParty.begin(); iter != vParty.end(); iter)
		{
			if (iter->find(aPerson) != iter->end())
			{
				for (int i : *iter)
				{
					if (isAffected[i] == 0)
					{
						isAffected[i] = 1;
						vAffected.push_back(i);
					}
				}
				iter = vParty.erase(iter);
			}
			else
				iter++;
		}

	}
	cout << vParty.size();
	return 0;
}

 

Note