[C++] 백준 1034 - 거짓말 (유니온 파인드는 모르겠고)

백준 1034 : 거짓말
난이도 : 골드 4

시간 : 40분 소요

 

 

 

문제

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

1043번: 거짓말

 

풀이 과정

 

해당 문제를 풀고, 여러 사람들의 풀이를 봤는데 다들 유니온 파인드 알고리즘을 사용해서 해결했었다.

이 기회를 통해 알게 되었지만 나는 해당 문제는 큐를 사용해서 풀었다.

비슷한? 동일한? 방법인지는 더 공부해봐야 겠다.

 

 

 

 변수 정의

int S[MAX];
vector<int> v[MAX];
queue<vector<int>> q;

 

1. S[i] == 1 : i번 사람은 진실을 알고 있거나 알게 될 사람이라는 의미

2. vector<int> v[i] : i번째 파티에 있는 사람들의 목록

3. queue<vector<int>> q : 진실을 알고 있거나 알게 될 사람이 있어 그 외의 사람들도 처리가 필요한 큐

 

구현

1. 입력 부분에서 진실을 아는 사람이 포함돼 있는 파티그룹을 큐에 넣는다.

2. 큐에 해당 그룹들을 빼서 해당 그룹에 있는 모든 사람들을 진실을 아는 명단에 넣고, 해당 명단을 비운다.

 

3. 진실을 아는 사람의 명단이 업데이트 되었기 때문에 다시 다른 파티에 진실을 아는 사람들이 있는지 확인한다.

  3-1. 있다면 해당 명단을 비우고, 큐에 넣는다.

 

4. 큐가 비어있지 않으면 거짓말을 해도 되는 집단임을 의미한다.

 

 

최종 코드

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

using namespace::std;

#define MAX 51

int N, M;
int Snum;
int S[MAX];
vector<int> v[MAX];
queue<vector<int>> q;

int main(){
    scanf("%d %d", &N, &M);
    scanf("%d", &Snum);
    
    for(int i=0; i<Snum; i++){
        int t;
        cin >> t;
        S[t] = 1;
    }
    
    for(int i=0; i<M; i++){
        int tmp;
        cin >> tmp;
        bool No = false;
        for(int j=0; j<tmp; j++){
            int person;
            
            cin >> person;
            v[i].push_back(person);
            
            if(S[person] == 1){
                No = true;
            }
        }
        if(No){
            q.push(v[i]);
            v[i].clear();
        }
    }
    
    while(!q.empty()){
        vector<int> tmp = q.front();
        q.pop();
        for(auto i : tmp){
            S[i] = 1;
        }
        
        for(int i=0; i<M; i++){
            for(auto j : v[i]){
                if(S[j] == 1){
                    q.push(v[i]);
                    v[i].clear();
                    break;
                }
            }
        }
    }
    
    int cnt = 0;
    for(int i=0; i<M; i++){
        if(!v[i].empty()){
            cnt++;
        }
    }
    
    cout << cnt << '\n';
    
}

 

 

 

잡담

유니온 파인드에 대해 알게 되었다!