[백준][1043] 거짓말

이 포스트는 백준 사이트의 거짓말 문제 풀이입니다.

문제

해결 과정

이 문제는 Union-Find 알고리즘을 사용하면 쉽게 풀 수 있는 문제입니다.

문제를 간단히 정리하면,
지민이 이야기의 진실을 아는 사람이 어떠한 질병에 감염된 사람이고
모르는 사람이 순수한 사람이라고 생각하면 쉽게 이해할 수 있습니다.
감염된 사람과 함께 있는 파티는 파티원 모두가 감염되고
새롭게 감염된 파티원은 다른 파티에서도 또 다른 파티원을 감염시킵니다.

이때, 순수한 사람만 있는 파티의 수를 구하면
문제의 정답을 알 수 있습니다.

문제 풀이의 순서는 아래와 같습니다.

1. M개의 파티원 정보를 받으면서 모든 파티원을 같은 집합으로 연결 (Union)
2. 진실을 알고 있는 파티원(감염된 파티원)을 순회하면서
   진실을 알게된 파티원을 새로운 집합으로 연결

위 과정을 통해 지민이가 참여할 수 있는 최대 파티 수를 계산할 수 있었습니다.

코드 구현

#include <iostream>
#include <vector>

using namespace std;

vector<int> parent;
vector<int> knowing_member;
vector<vector<int>> party_list;

void input();
int Find(int curr);
void Union(int a, int b);
int get_funny_party_count();


int main()
{   
    input();
    cout << get_funny_party_count();
    return 0;
}


void input() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N, M;
    cin >> N >> M;
    
    parent.assign(N + 2, 0);
    for(int i = 1; i <= N + 1; ++i) {
        parent[i] = i;
    }

    int know_cnt;
    cin >> know_cnt;
    knowing_member.assign(know_cnt, 0);
    for(int i = 0; i < know_cnt; ++i) {
        cin >> knowing_member[i];
    }

    party_list.assign(M, vector<int>());
    for(int party_number = 0;  party_number < M; ++party_number) {
        int member_cnt;
        cin >> member_cnt;

        int prev, curr;
        for(int curr_num = 0; curr_num < member_cnt; ++curr_num) {
            if(curr_num == 0) {
                cin >> prev;
            } else {
                cin >> curr;
                Union(prev, curr);
                prev = curr;
            }
            party_list[party_number].push_back(prev);
        }
    }
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a < b) {
        parent[b] = a;
    } else {
        parent[a] = b;
    }
}

int Find(int curr) {
    if(curr == parent[curr]) return curr;
    else return parent[curr] = Find(parent[curr]);
}

int get_funny_party_count() {
    int fun_party_cnt = 0;
    for(const auto& party : party_list) {
        bool can_funny_story = true;
        for(const auto& member : party) {
            for(const auto& know_mem : knowing_member) {
                if(Find(know_mem) == Find(member)) {
                    can_funny_story = false;
                    break;
                }
            }
            
            if(false == can_funny_story) {
                break;
            }
        }

        if(can_funny_story) {
            fun_party_cnt += 1;
        }
    }

    return fun_party_cnt;
}

실행 결과