[Algorithm] 1043: 거짓말

• toc {:toc}

📦1043: 거짓말

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-08
문제 확인하기

풀이

• vector의 이름 설정이 헷갈려서 풀이가 느렸다.

• 사전 설정

1. party[i]는 i 번째 사람이 참가하는 파티 번호를 의미한다.
2. participant[i]는 i 번째 파티에 참여하는 참가자의 번호 모음을 의미한다. 즉, 1번째 파티에서 1, 2, 3, 4가 참여하는 경우 participant[1]에는 {1, 2, 3, 4}가 들어있다.

• 풀이

1. 진실을 알고 있는 사람들을 큐에 넣는다.
2. BFS를 진행하면서 진실을 알고 있는 사람과 함께 파티에 참여하는 사람들의 번호를 모두 체크한다.
3. 한 파티 안에서 진실을 알고 있는 사람이 없다면 res를 증가시킨다.
4. res를 최종 출력한다.

#include <iostream>
#include <vector>
#include <queue>
#define endl '\n';
using namespace std;
 
vector<int> party[51] = {};  // N, i번째 사람의 참가하는 파티 번호
vector<int> participant[51] = {};  // M, 파티 참가자
int truth[51];
int N, M, res=0;
queue<int> q;
 
void Input(){
    cin >> N >> M;
    int val;
    cin >> val;
    for(int j=1; j<=val; j++){
        int number;
        cin >> number;
        truth[number] = 1;
        q.push(number);
    }
    for(int i=1; i<=M; i++){
        int val;
        cin >> val;
        for(int j=1; j<=val; j++){
            int number;
            cin >> number;
            party[number].push_back(i);
            participant[i].push_back(number);
        }
    }
}
 
void bfs(){
    while(!q.empty()){
        int number = q.front(); q.pop();
        for(auto partyNum : party[number]){
            for(auto temp : participant[partyNum]){
                if(truth[temp] == 1) continue;
                truth[temp] = 1;
                q.push(temp);
            }
        }
    }
}
 
void Solution(){
    bfs();
    for(int i=1; i<=M; i++){
        int flag = 1;
        for(auto number : participant[i]){
            if(truth[number]==1){
                flag = 0;
                break;
            }
        }
        if(flag){
            res++;
        }
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    Input();
    Solution();
    cout << res << endl;
 
    return 0;
}