[백준,c++] 1043번 - 거짓말

문제

1043번: 거짓말

 

코드

#include <iostream>
#include <vector>
using namespace std;

int parent[101];
int N, M;

void union_parent(vector<vector<int>> &party){
    for(int i=0; i<party.size(); i++){
        bool flag = false;
        for(int k=0; k<party[i].size(); k++){
            if(parent[party[i][k]] == -1){
                flag = true;
                break;
            }
        }
        if(flag){
            for(int k=0; k<party[i].size(); k++){
                parent[party[i][k]] = -1;
            }
        }
    }
    for(int i=party.size()-1; i>=0; i--){
        bool flag = false;
        for(int k=0; k<party[i].size(); k++){
            if(parent[party[i][k]] == -1){
                flag = true;
                break;
            }
        }
        if(flag){
            for(int k=0; k<party[i].size(); k++){
                parent[party[i][k]] = -1;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N>>M;
    int know; cin>>know;
    for(int i=0; i<know; i++){
        int peo; cin>>peo;
        parent[peo] = -1;
    }
    
    vector<vector<int>> party;
    
    for(int i=0; i<M; i++){
        int cnt; cin>>cnt;
        vector<int> temp;
        for(int k=0; k<cnt; k++){
            int peo; cin>>peo;
            temp.push_back(peo);
        }
        party.push_back(temp);
    }
    
    int cnt = 50;
    while(cnt--) union_parent(party);

    int ans = 0;
    for(int i=0; i<party.size(); i++){
        bool flag = true;
        for(int k=0; k<party[i].size(); k++){
            if(parent[party[i][k]] == -1){
                flag = false;
                break;
            }
        }
        if(flag) ans ++;
    }
    
    cout<<ans;
}

 

풀이

문제 분류는 유니온 파인드이지만 입력값이 50밖에 들어오지 않기 때문에 브루트포스를 이용해서 구현으로 풀었습니다.

진실을 아는 사람의 경우 parent[사람] = -1로 세팅해주고, 모든 파티를 탐색하면서 진실을 아는 사람이 해당 파티에 존재하는 경우 그 파티에 존재하는 모든 사람을 진실을 아는 사람으로 세팅했습니다.

input:
4 5
1 1
1 1
1 2
1 3
2 4 2
2 4 1
answer: 1

다만 위와 같은 입력처럼 파티의 순서에 의존하지 않아야 하기 때문에 파티 탐색을 앞에서 도는 경우와 뒤에서 도는 경우로 수행했습니다.

input:
6 5
1 6
2 4 5
2 1 2
2 2 3
2 3 4
2 5 6
answer: 0

또한 파티 탐색을 앞 뒤로 총 한 번만 하는 경우 위와 같은 입력에서 사람 2, 3이 갱신되지 않기 때문에 파티의 총 갯수인 50만큼 반복하도록 수행했습니다.