[BOJ] 1043 - 거짓말 (C++)

문제

거짓말

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, F;
bool fact[51];

int getParent(int parent[], int a){
    if (parent[a] == a) return a;
    return parent[a] = getParent(parent, parent[a]);
}

void unionParent(int parent[], int a, int b){
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

int findParent(int parent[], int a, int b){
    a = getParent(parent, a);
    b = getParent(parent, b);
    if (a == b) return 1;
    return 0;
}

int main(void){
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> N >> M >> F;
    
    if (F == 0) { cout << M; return 0; }

    int parent[N+1];
    for (int i = 1; i <= N; i++) parent[i] = i;

    vector<int> truth;
    for (int i = 0; i < F; i++){
        int x;
        cin >> x;
        truth.push_back(x);
    }

    vector< vector<int> > party;
    for (int i = 0; i < M; i++){
        int x, num;
        vector<int> temp;
        
        cin >> x;
        for (int j = 0; j < x; j++){
            cin >> num;
            temp.push_back(num);
        }
        party.push_back(temp);

        for (int j = 1; j < temp.size(); j++) unionParent(parent, temp[j-1], temp[j]);
    }

    int cnt = 0;
    bool flag;
    for (int i = 0; i < party.size(); i++){
        flag = true;

        for (int j = 0; j < party[i].size(); j++){
            for (int k = 0; k < truth.size(); k++){
                if (findParent(parent, party[i][j], truth[k])){
                    flag = false;
                    break;
                }
            }
            if (!flag) break;
        }
        if (flag) cnt++;
    }

    cout << cnt;
    return 0;
}

접근

알고리즘 문제를 풀면서 union-find 문제는 거의 풀어보지 않았던 터라 풀이의 도움을 받았다. 아래와 같은 과정을 통해 해결하였다. 기본적으로 union-find를 접해보았다면 나름 어렵지 않게 해결할 수 있는 문제 같았다.

1. 각 파티에 오는 사람들끼리 연결시킨다. (unionParent)
2. 전체 파티의 인원수만큼 반복문을 돌며 처음 입력받았던 진실을 아는 사람과 연결되었는지 확인한다. (findParent)
  2-1. 해당 파티에 진실을 아는 사람과 연결된 사람이 존재한다면? 그 파티에서는 거짓말을 할 수 없으므로 반복문 탈출
  2-2. 해당 파티에 진실을 아는 사람과 연결된 사람이 존재하지 않는다면? 정답 증가
  

참고
https://9x211x2.tistory.com/34