[백준][C++] 1043번: 거짓말 <200>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

생각의 흐름

이번문제는 Union Find 알고리즘을 알아야 해결하기 쉽다.

 

관련 내용을 정리한 글이 있으니 먼저 읽어보기를 권장한다!

[알고리즘] Union Find 알고리즘 : 경로 압축

 

"진실을 언제가는 알 수 있는 사람으로 이루어진 집합" 과 "진실을 절대 알 수 없는 사람으로 이루어진 집합" 으로 나눠야 한다.

 

우선 이렇게 2개의 집합으로 나눈 후에,

각 파티마다 오는 사람들을 탐색하면서 해당 파티에 오는 모든 사람들이 "진실을 절대 알 수 없는 사람으로 이루어진 집합"에 해당된다면

=> 그 파티에서 거짓말을 할 수 있다!

 

각 파티의 경우마다 오는 사람들의 번호를 vector<int> adj 에 담아주었다. 총 2번 사용하게 되기 때문이다.

1) 처음 사람들을 union 시킬때

2) 거짓말을 할 수 있는 파티인지를 확인할 때

 

맨 처음 모두 자신의 부모로 자기 자신을 가리키도록 해준다.

parent[1]은 1, parent[2] 는 2 ... 이런식으로 말이다!

 

이후 각 파티를 돌면서 Union 연산을 통해 각 사람들을 집합으로 만들어준다.

맨 처음 진실을 알고 있는 사람과 같은 집합이 되면 이들 모두 진신을 알게되는 것 이다.

이렇게 각 사람들을 전부 집합으로 만들면, 진실을 알지 못하는 group이 생긴다. 이들이 핵심이다!

 

이후 다시 파티를 돌면서 해당 파티에 진실을 모르는 사람만 있다면 가능한 case이다!

이렇게 전부 확인해주면 된다!

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 51

int N, M;
int res;
int parent[MAX];
vector<int> adj[MAX];
vector<int> know_person;

int findParent(int num) {
    if(parent[num] == num) {
        return num;
    }
    return parent[num] = findParent(parent[num]);
}

void joinGroup(int a, int b){
    int pA = findParent(a);
    int pB = findParent(b);

    if(pA != pB) {
        parent[pA] = pB;
    }
}

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

    cin >> N >> M;

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

    int knowPerson = 0;
    cin >> knowPerson;

    int num;
    for (int i = 0; i < knowPerson; i++) {
        cin >> num;
        know_person.push_back(num);
    }
    for (int i = 1; i <= M; i++) {
        cin >> num;
        int personNumber;
        for (int j = 0; j < num; j++) {
            cin >> personNumber;
            adj[i].push_back(personNumber);
        }
    }

    for (int i = 1; i <= M; i++){
        int N1 = adj[i][0];
        for (int j = 1; j < adj[i].size(); j++){
            int N2 = adj[i][j];
            joinGroup(N1, N2);
        }
    }

    for(int i = 1; i <= M; i++) {
        bool flag = false;
        for(int j = 0; j < adj[i].size(); j++) {
            int N1 = adj[i][j];
            for(int k = 0; k < know_person.size(); k++){
                int N2 = know_person[k];
                if(findParent(N1) == findParent(N2)) {
                    flag = true;
                    break;
                }
            }
            if(flag == true) break;
        }
        if(flag == false) {
            res++;
        }
    }

    cout << res;

    return 0;
}