[백준] 1043. 거짓말

문제

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

풀이

개인적인 견해론 문제를 제대로 이해하지 않으면 접근하기가 쉽지 않을 것이라 생각한다. 모든 파티를 참가하면서 진실을 알고 있는 사람들이 참가했던 파티에선 진실만을, 그렇지 않으면 거짓말을 해도 되는데, 이 말 뜻이 무엇인지 잘 생각해봐야한다. 

일단 처음에 진실을 알고 있는 사람들이 주어진다. 그렇다면 이 사람들이 참가한 파티에선 무조건 진실만을 얘기해야한다. 그럼 나머지 파티에선 거짓말을 해도 될까? 물론 아니다. 원래 진실을 알고 있던 사람들이 참가한 파티에는 해당 이야기가 진실인지 거짓인지 몰랐던 사람들  또한 참가할 수 있다. 이 사람들을 unknown 라고 하자. unknown들도 현재 파티가 아닌 다른 파티에 참가할 수 있다. 

따라서 처음부터 알고 있던 사람들이 참가한 파티 내의 unknown들도 그 이야기를 진실로 알고 있을테고, 이 unknown 들이 참가한 파티에서도 진실을 말해야하고, 또 새로운 unknown들이 생기고.... 의 과정이 반복된다. 

이 과정이 끝나면 각 파티에서 생긴 모든 unknown들이 한명도 참여하지 않은 파티가 발생할 수 있다. 드디어 이 파티에서는 거짓말을 해도 되는 것이다! (물론 모든 unknown 들이 모든 파티에 한명이라도 들어갔다면 거짓말을 칠 수 있는 파티는 없을 수도 있는 것이다.)

이제 이 문제는 BFS 나 DFS 같은 완전 탐색으로 해결할 수 있다는 것을 알 수 있게 되었다. 아래와 같은 알고리즘으로 구현할 수 있게 된다.

1. queue에 원래부터 진실을 알고 있던 사람들이 참석한 파티들을 모두 넣는다. 이 파티들은 진실 파티 목록에 넣어준다.

2. queue가 빌 때까지 queue에 들어있는 파티를 하나씩 탐색한다. 

    1) 해당 파티에 참석한 사람들을 모두 탐색한다.

    2) 이 사람들이 참석한 파티들을 모두 탐색한다.

    3) 이 탐색된 파티들은 진실을 말해야하는 파티가 된다. 이 파티가 진실 파티인지 아직 파악이 안 된 파티라면 queue에 넣어준다.

3. 해당 과정이 끝난 후, M개의 파티를 체크하면서, 진실 파티 목록에 없는 파티들의 개수를 세어준다.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>

using namespace std;

int N, M, NC;
vector<vector<int> > party;
vector<int> participant[51];
int know[51] = { 0, };
queue<int> q;
int trueparty[51];

int main(){

    ios::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;
    cin >> NC;
    for(int i = 0; i < NC; i++){
        int t; cin >> t; know[t] = 1;
    }
    for(int i = 0; i < M; i++){
        vector<int> tmp; party.push_back(tmp);
        int pn; cin >> pn;
        for(int j = 0; j < pn; j++){
            int n; cin >> n;
            party[i].push_back(n);
            participant[n].push_back(i);
            if(know[n] == 1){
                q.push(i);
            } 
        }
    }

    while(!q.empty()){
        int p = q.front(); q.pop();
        trueparty[p] = 1;
        for(int i = 0; i < party[p].size(); i++){
            int member = party[p][i];
            for(int j = 0; j < participant[member].size(); j++){
                int curparty = participant[member][j];
                if(trueparty[curparty] == 0){
                    q.push(curparty);
                }
            }
        }
    }
    int cnt = 0;
    for(int i = 0; i < M; i++){
        if(trueparty[i] == 0) cnt++;
    }
    cout << cnt;
    return 0;
}