백준 1043 거짓말

1. 문제 링크

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

1043번: 거짓말

 

2.  풀이

 

문제의 핵심은 

진실을 알고 있는 사람이 참석한 파티를 모두 제거하는 것 

 

파티에 대한 참석자 배열과 참석자에 대한 파티 배열 2개를 만든 후 BFS방식을 통해 진실을 알고 있는 사람이 참석한 모든 파티를 제거할 수 있다. 간단한 알고리즘은 아래와 같다.

 

1. 최초에 진실을 알고있는 사람을 모두 queue에 push 
2. qeueue가 비워질 때까지
   1.  queue에서 원소 하나 pop(진실을 알고 있는 사람) 
   2.  진실을 알고 있는 사람이 참석한 모든 파티에 대해(참석자에 대한 파티 배열을 통해 조회), 아직 거짓 파티로 표시된 경우 => 진실의 파티로 표시
   3.  1에서 진실의 파티로 표시된 파티에 참석한 모든 사람들에 대해(파티에 대한 참석자 배열을 통해 조회), 아직 거짓말을 할 수 있는 사람은 => 모두 진  실을 들은 것으로 표시하고 queu에 push

   3. 거짓 파티로 지정되어 있는 개수를 카운트 후 리턴

 

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

using namespace std;

int N, M;
vector<int> partyToPerson[51];
vector<int> personToParty[51];
bool truthKnowPerson[51];
bool falsehoodParty[51];
queue<int> checkPersonQ;

void InputAndInit() {
	cin >> N >> M;
	for (int i = 0; i < 51; i++) {
		partyToPerson[i].clear();
		personToParty[i].clear();
		truthKnowPerson[i] = false;
		falsehoodParty[i] = true;
	}
	while (!checkPersonQ.empty())
		checkPersonQ.pop();

	//진실을 아는 사람
	int tmp, kownPerson;
	cin >> tmp;
	for (int i = 0; i < tmp; i++) {
		cin >> kownPerson;
		truthKnowPerson[kownPerson] = true;
		checkPersonQ.push(kownPerson);
	}

	int candidatePerson;
	//파티 참석자
	for (int partyNum = 1; partyNum <= M; partyNum++) {
		cin >> tmp;
		for (int i = 0; i < tmp; i++) {
			cin >> candidatePerson;
			partyToPerson[partyNum].push_back(candidatePerson);
			personToParty[candidatePerson].push_back(partyNum);
		}
	}
}

int main() {
	InputAndInit();

	while (!checkPersonQ.empty()) {
		int truthPerson = checkPersonQ.front(); checkPersonQ.pop();
		for(int nextParty : personToParty[truthPerson]){				//진실을 알고있는 사람이 참석한 모든 파티에 대해
			if (falsehoodParty[nextParty]) {							//아직 거짓말 파티를
				falsehoodParty[nextParty] = false;						//진실된 파티로 바꾸고								
				for (int nextTruthPerson : partyToPerson[nextParty]) {	//바꾼 진실된 파티에 참석한 모든 사람에 대해
					if (truthKnowPerson[nextTruthPerson] == false) {	//아직 이 사람이 진실을 모른다면
						truthKnowPerson[nextTruthPerson] = true;		//진실을 알도록 표시 후
						checkPersonQ.push(nextTruthPerson);				//큐에 넣어서 다음 번에 이 사람이 참석한 파티에 대해 알아본다.
					}
				}
			}
		}
	}
	int answer = 0;
	for (int i = 1; i <= M; i++) {
		if (falsehoodParty[i])
			answer++;
	}
	cout << answer << "\n";
	return 0;
}