[백준] #1047. 거짓말

문제는 여기서 확인할 수 있다. BaekJoon #1047. 거짓말

---

💀 시행착오

👇 풀이를 보러 온거라면 아래에 POINT로 바로 내려가면 된다. 👇

문제를 읽어보고 "앗 설마 Union Find 문제인가?" 했는데 다른 방법으로 바득바득 풀어보려다가 한시간 넘게 날렸다. 가끔은 촉을 따라보자...

파티에 온 사람을 비교하는 거니까 bitset으로 n번째 사람이 참석했으면
1로 바꿔서 & 연산으로 빠르게 비교해야지ㅎㅎ 하고 풀었는데 파티에 순서가 있다는 언급이 없었다는 것을 코드를 다 짜고 알았다🤦‍♂️

순서가 없는 상태에서 파티에 온 사람과 온 사람과 함께 참석한 사람, 그리고 그 사람이 참석한 파티에 참석한 사람, 또 참석하고....
암튼 간에 걍 트리로 관계도를 전부 만들어두고 탐색을하던가 해야하는 문제다. 막무가내로 전부 비교하려고하면 비효율적 + 시간초과 엔딩이다.

---

🤔 POINT

1. Union-Find Tree

파티를 하나의 집합으로 보자.
진실을 아는 사람이 포함된 집합이 있으면 해당 집합의 나머지 요소들도 진실을 아는 사람이 된다. 그럼 이 첫 집합과 교집합을 갖고 있는 다른 집합들도 진실을 알게된다. 이렇게 조금씩 영역을 넓혀가는 거로 볼 수 있다.
이런 땅따먹기(?)식의 문제는 유니온 파인드 트리로 간단하게 해결할 수 있다.

• 유니온 파인드 트리는 parent[] 배열을 이용해 각 노드의 부모 노드가 어느 노드인지를 명시한다. 초기에 parent[i] = i로 각 노드가 각각 분리되어 있다.

• A와 B의 트리를 합칠 때는 parent[parent[B]] = parent[A] 이런 식으로 A의 parent를 B의 parent의 parent로 설정해준다.

• 그런데 이렇게 할 경우에 트리의 depth가 계속해서 증가한다. 나중에find 연산을 할 때 너무너무 비효율적이다.

• 그래서 parent를 불러올 때 get_parent() 함수를 만들어서 트리의 아랫부분이 모두 root 노드를 부모로 갖도록 만들어준다. 아래 그림을 보면 이해가 될 것 같다.
  

• depth가 깊어지지 않도록 찾을 때마다 root가 부모가 되도록 업데이트 해주는 과정은 아래와 같이 구현할 수 있다.

int get_parent(int (&parent)[55], int g){
    if(parent[g] == g){
        return g;
    }
    else{
        return parent[g] = get_parent(parent, parent[g]);
    }
}

• 그러면 A노드와 B노드의 Union과정은 이렇게 표현할 수 있다.
  parent[get_parent(parent, A)] = get_parent(parent, B);
• Find는 위에서 사용한 get_parent() 함수로 루트 노드가 같은지 비교함으로 같은 소속인지 확인할 수 있다.
  

2. 풀이 과정

위에서 설명했던 유니온 파인드로 진실을 알게된 사람을 확인했다.
입력이 주어지면 첫 번째 사람이 parent가 되도록 트리를 만들었다.
파티 참석자를 이후 비교해야하기 때문에 bitset을 이용해서 각 파티에 참석한 인원을 체크했다.

void make_party_group(int party, int (&parent)[55], bitset<55> (&party_list)[55]){
    int pppl, input, g_parent;
    for(int i=0; i<party; i++){
        scanf("%d", &pppl);
        for(int p=0; p<pppl; p++){
            scanf("%d", &input);
            party_list[i][input] = 1;
            if(p==0) g_parent = get_parent(parent, input);
            else{
                parent[get_parent(parent, input)] = g_parent;
            }
        }
    }
    return;
}

이제 진실을 안 사람들이 누구누구인지 확인해야한다.
가장 처음에 주어진 사람들과 같은 부모를 공유하는 노드를 bitset에 체크한다.

void get_truth_bit(int ppl, int tppl, int (&parent)[55], vector<int> &truth, bitset<55> &truth_bit){

    for(int i=0; i<tppl; i++){
        int t = truth[i];
        int tp = get_parent(parent, t);
        truth_bit[t] = 1;

        for(int j=1; j<=ppl; j++){
            if(tp == get_parent(parent, j)){
                truth_bit[j] = 1;
            }
        }
    }
    return;
}

이렇게 되면 나중에 진실을 아는 사람이 파티에 참석했는지 체크하는 연산이 쉬워진다. & 연산 한번이면 끝나기 때문이다.

int count_lie_party(int party, bitset<55> &truth_bit, bitset<55> (&party_list)[55]){
    int cnt = 0;
    bitset<55> comp;
    for(int i=0; i<party; i++){
        comp.reset();
        comp = truth_bit & party_list[i];
        if(!comp.any()) {
            cnt++;
        }
    }
    return cnt;
}

전체 코드는 아래와 같다.

//BaekJoon_1043
//거짓말
/*
* 제한 시간 : 2s
* 정답 비율 : 33.551%
*/

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

void init(int ppl, int tppl, vector<int> &truth, int (&parent)[55]){
    int input = 0;
    for(int i=0; i<tppl; i++){
        scanf("%d", &input);
        truth.push_back(input);
    }

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

    return;
}

int get_parent(int (&parent)[55], int g){
    if(parent[g] == g){
        return g;
    }
    else{
        return parent[g] = get_parent(parent, parent[g]);
    }
}

void make_party_group(int party, int (&parent)[55], bitset<55> (&party_list)[55]){
    int pppl, input, g_parent;
    for(int i=0; i<party; i++){
        scanf("%d", &pppl);
        for(int p=0; p<pppl; p++){
            scanf("%d", &input);
            party_list[i][input] = 1;
            if(p==0) g_parent = get_parent(parent, input);
            else{
                parent[get_parent(parent, input)] = g_parent;
            }
        }
    }
    return;
}
void get_truth_bit(int ppl, int tppl, int (&parent)[55], vector<int> &truth, bitset<55> &truth_bit){

    for(int i=0; i<tppl; i++){
        int t = truth[i];
        int tp = get_parent(parent, t);
        truth_bit[t] = 1;

        for(int j=1; j<=ppl; j++){
            if(tp == get_parent(parent, j)){
                truth_bit[j] = 1;
            }
        }
    }
    return;
}

int count_lie_party(int party, bitset<55> &truth_bit, bitset<55> (&party_list)[55]){
    int cnt = 0;
    bitset<55> comp;
    for(int i=0; i<party; i++){
        comp.reset();
        comp = truth_bit & party_list[i];
        if(!comp.any()) {
            cnt++;
        }
    }
    return cnt;
}
int main(){
    int ppl, party, tppl, input;
    int parent[55];
    vector<int> truth;
    bitset<55> truth_bit;
    bitset<55> party_list[55];

    scanf("%d %d", &ppl, &party);
    scanf("%d", &tppl);

    init(ppl, tppl, truth, parent);
    make_party_group(party, parent, party_list);
    get_truth_bit(ppl, tppl, parent, truth, truth_bit);
    int lie_party = count_lie_party(party, truth_bit, party_list);
    printf("%d\n", lie_party);

    return 0;
}

💬 주저리

유니온 파인드 설명을 열심히 적고 다시 읽어보는데 처음 보는 사람이 이해할 수 있을까하는 의문점이 든다... 알고리즘이 아니라 글쓰는 것부터 연습해야 할지도..😂 내가 아는 거를 잘 설명하는 것도 능력이다 싶다. 쓰다보면 조금씩 늘겠지!!

끝 ✌