[백준/BOJ] 1043번 거짓말

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

1043번: 거짓말

 

문제를 정확하게 읽자고 반성하게 만든 문제,,,

나는 진실을 알고 있는 사람 수만 나오고 아는 사람이 누군지는 안 나오는 줄 알고 열심히 조합으로 만들어서 돌렸는데,

매우 멍청한 행동이었다ㅜㅜ. 어쩐지 계속 틀렸다고 하더라,,,

 

1 .진실을 아는 사람들이 참석한 모든 파티를 체크하고

2. 해당파티를 참석한 다른 사람들이 참석한 파티들도 모두 체크한다.

3. 그럼 또다시 그 파티들을 참석한 사람들이 참석한 다른 파티도 체크한다.

4.  .... 이런식으로 연쇄작용을 거치면서 진실을 아는 사람들이 참석한 모든 파티를 체크한다.

마지막에 파티의 체크 여부를 확인하여 과장을 할 수 있는지 확인하면 된다.

 

문제 자체는 난이도가 높지는 않은 편.

 

 

 

 

 

 

<정답 코드>

 

#include<iostream>
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<stack>
using namespace std;
vector<vector<int>>party;
vector<vector<int>>present;
vector<vector<int>>ban;
int choose[55];
int N, M;
int re;
int know;
bool ck[55] = { false };
void func3(int person);
bool ckperson[55] = { false };

void func4(int num) {
	for (int i = 0; i < party[num].size(); i++) {
		if(!ckperson[party[num][i]])func3(party[num][i]);
	}
	return;
}

void func3(int person){
	ckperson[person] = true;
	for (int i = 0; i < present[person].size(); i++) {
			ck[present[person][i]] = true;
			func4(present[person][i]);
	}
	return;
}


void func(void) {

		int cnt = 0;
		bool banparty[55] = { false };
		for (int k = 0; k <know; k++) {
			for (int p = 0; p < ban[choose[k]].size(); p++) {
				if (!banparty[ban[choose[k]][p]]) {
					banparty[ban[choose[k]][p]] = true;
					cnt++;
				}
			}
		}
		re =M-cnt;
		return;
	
}



int main(void){
	
	scanf("%d %d", &N,&M);
	party.resize(M+1);
	present.resize(N + 1);
	ban.resize(N + 1);
	
	scanf(" %d", &know);
	for (int i = 0; i < know; i++)scanf(" %d", &choose[i]);
	for (int i = 1; i <= M; i++) {
		int people;
		scanf(" %d", &people);
		for (int j = 0; j < people; j++) {
			int person;
			scanf(" %d", &person);
			party[i].push_back(person);
			present[person].push_back(i);
		}
	}
	for (int i = 1; i <= N; i++) {
		memset(ck, false, sizeof(ck));
		memset(ckperson, false, sizeof(ckperson));
		func3(i);
		for (int j = 1; j <= M; j++)if (ck[j])ban[i].push_back(j);
	}
	func();
//	printf("%d", ban[1][1]);
	printf("%d\n", re);


	return 0;
}