[ 백준 / C++ ] 1043 : 거짓말

[ 문제 ]

 

1043번: 거짓말 (acmicpc.net)

 

[ 접근방법 ]

 

파티에서 거짓말을 들은 사람은 다른 파티에서 무조건 거짓말만을 들어야 한다.

 

따라서 진실을 아는 사람과 엮인 사람들은 무조건 진실을 들어야 한다.

 

처음에는 BFS를 활용하여 진실을 들어야 하는 사람을 미리 구한다.

 

그 후, 각 파티에 진실을 들어야 하는 사람이 존재하는지를 체크해준 후 없어도 된다면
거짓말을 해준다.

 

[ 소스코드 ]

 

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

using namespace std;

int n, m, k, a, b, ans;
bool known[55], chk;
vector<int> party[55], vec[55];
queue<int> que;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    
    while(k--){
        cin >> a;
        que.push(a);
        known[a] = true;
    }

    for(int i = 0; i < m; i++){
        cin >> k >> a;
        party[i].push_back(a);
        while(--k){
            cin >> b;
            party[i].push_back(b);
            vec[a].push_back(b);
            vec[b].push_back(a);
        }
    }

    while(!que.empty()){
        int qf = que.front();
        que.pop();
        for(auto i : vec[qf]){
            if(known[i])continue;
            que.push(i);
            known[i] = true;
        }
    }

    for(int i = 0; i < m; i++){
        chk = true;
        for(auto j : party[i]){
            if(known[j]){
                chk = false;
                break;
            }
        }
        if(chk)ans++;
    }
    
    cout << ans;

    return 0;
}