[C++] 백준 1043 거짓말

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int n,m;
 
// 진실을 아는 사람 저장 
vector<int> true_person;
 
// false 일 경우 거짓말 가능 
bool check_party[51];
 
// 파티에 오는 사람 
vector<int> party[51];
 
// 이 사람이 가는 파티 저장 
vector<int> person[51];
 
 
void input() {
    cin >> n >> m;
    int tmp,a,b;
    cin >> tmp;
    
    for(int i=0; i<tmp; i++) {
        cin >> a;
        true_person.push_back(a);
    }
    
    for(int i=0; i<m; i++) {
        cin >> a;
        for(int j=0; j<a; j++) {
            cin >> b;
            party[i].push_back(b);
            person[b].push_back(i);
        }
    }
}
 
void bfs() {
    queue<int> q;
    for(int i=0; i<true_person.size(); i++) {
        for(int j=0; j<person[true_person[i]].size(); j++) {
            q.push(person[true_person[i]][j]);
        }
    }
    
    while(!q.empty()) {
        // 파티 검색 
        int x = q.front();
        check_party[x] = true;
        q.pop();
        
        for(int i=0; i<party[x].size(); i++) {
            int pp = party[x][i];
            for(int j=0; j<person[pp].size(); j++) {
                if(check_party[person[pp][j]]) continue;
                q.push(person[pp][j]);
            }
        }
    }
} 
 
 
int main() {
    input();
    bfs();
    int result = 0;
    for(int i=0; i<m; i++) {
        if(!check_party[i]) result++;
    }
    cout << result;
}

 

살짝 말을 어렵게 풀어낸 bfs 문제 

 

 

1. 진실을 아는 사람이 참가하는 파티를 큐에 저장

2. 진실을 아는 사람이 참가하는 파티에 참가하는 사람들이 참가하는 파티 또한 큐에 저장  (이 논리를 생각하는게 어렵다)

 

진실을 아는 사람이 참가하는 파티 == x 

진실을 아는 사람이 참가하는 파티에 참가하는 사람들 == party[x][i]

진실을 아는 사람이 참가하는 파티에 참가하는 사람들이 참가하는 파티 == person[party[x][i]][j]

 

 

while(!q.empty()) {
        // 파티 검색 
        int x = q.front();
        check_party[x] = true;
        q.pop();
        
        for(int i=0; i<party[x].size(); i++) {
            int pp = party[x][i];
            for(int j=0; j<person[pp].size(); j++) {
                if(check_party[person[pp][j]]) continue;
                q.push(person[pp][j]);
            }
        }
    }

 

중요한건 거짓말을 칠 수 있는 파티를 계산하는 것이기 때문에 큐를 돌릴때 큐의 인자가 파티가 기준이 되어야한다.

 

역시 거짓말 치는건 주변인의 주변인까지 속여야 하는 어려운 작업이니까 거짓말 치지말고 살도록 하자