[ 백준 1043 ] 거짓말 (C++)

백준의 거짓말(1043) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

거짓말을 할 수 있는 파티 갯수의 최댓값을 구해야 하는 문제이다.

접근 방법을 떠올리는데 생각보다 어려웠던 문제이다. 본인은 이 문제를 Union-Find 알고리즘을 통해서 접근하였다.

쉽게 생각해서, "진실을 언제가는 알 수 있는 사람으로 이루어진 집합" 과 "진실을 절대 알 수 없는 사람으로 이루어진 집합"

이렇게 2개의 묶음으로 나누었다는 이야기이다. 이렇게 나눈다면 ? 각 파티에 오는 사람들을 탐색하면서 해당 파티에 오는

모든 사람들이 "진실을 절대 알 수 없는 사람으로 이루어진 집합"에 해당하는 사람들로만 이루어져 있다면, 그 파티에서는 거짓말을 할 수 있다 라고 판단할 수 있다.

일단 가장 먼저, 각 파티에 오는 사람들을 다 하나로 묶어주었다. Parent[] 라는 int형 배열을 만들어서, 같은 파티에 오는 사람들

끼리는 모두 Parent가 동일하게 만들어주었다.(Union)

문제에 나와있는 입력 예시를 통해서 구체적으로 알아보자.

* 진실을 아는 사람의 수 = 0 명

* 1번 파티에 오는 사람 = { 1, 2 }

* 2번 파티에 오는 사람 = { 3 }

* 3번 파티에 오는 사람 = { 2, 3, 4 }

그럼 각 파티에 오는 사람들끼리 한번 묶어보자. 이 과정을 'Parent'라는 하나의 배열을 이용해서 구현하였는데, 초기의 Parent값은 자기자신을 나타내고 있다.

즉, 1번 사람의 Parent값은 1 , 2번 사람의 Parent값은 2, x번 사람의 Parent값은 x 인 것이다.

이 때, 1번 파티에 오는 사람을 합쳐보자. 그렇게 되면 Parent[1] = 1 , Parent[2] = 1 이 될 것이다.

2번 파티에 오는 사람은 한 명이므로 합칠 수가 없다. 3번 파티에 오는 사람을 합쳐보자. 그럼 결과는 다음과 같아질 것이다.

Parent[2] = Parent[3] = Parent[4] = 1. 왜냐하면 Parent[2]의 값이 '1'이 였기 때문에 1로 모두 같아질 것이다.

이렇게 모두 부모를 합친 후에는 해당 파티에 갈 수 있는지 체크를 해주어야 한다. 체크를 하기 방법은 다음과 같다.

"파티에 가는 사람 한명 한명을, 진실을 알고 있는 사람 한명 한명씩 모두 비교해본다."

물론 ! 파티에 가는 사람도, 진실을 알고있는 사람도 모두 위에서 구해놓은 'Parent'의 값을 통해서 비교를 해야한다.

즉 ! 파티에 가는 사람의 Parent 값과, 진실을 알고 있는 사람의 Parent 값이 같다면, 결국 이 사람은 결국 언젠가는

진실을 알게 되는 사람이 된다. 하지만 ! 현재 파티에 가는 사람이, 진실을 알고있는 그 누구와도 Parent값이 같지 않다면 ?

그 사람은 진실을 알고있는 누구와도 마주치지 않는다는 이야기이고, 거짓말을 해도 된다는 것을 의미한다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 55
using namespace std;
 
int N, M, Answer;
int Parent[MAX];
vector<int> Know_Truth;
vector<int> Party[MAX];
 
void Input()
{
    cin >> N >> M;
    int K; cin >> K;
    for (int i = 0; i < K; i++)
    {
        int a; cin >> a;
        Know_Truth.push_back(a);
    }
    for (int i = 0; i < M; i++)
    {
        int Num; cin >> Num;
        for (int j = 0; j < Num; j++)
        {
            int a; cin >> a;
            Party[i].push_back(a);
        }
    }
    Answer = M;
}
 
int Find_Parent(int A)
{
    if (A == Parent[A]) return A;
    return Parent[A] = Find_Parent(Parent[A]);
}
 
void Union(int A, int B)
{
    A = Find_Parent(A);
    B = Find_Parent(B);
    Parent[B] = A;
}
 
bool Same_Parent(int A, int B)
{
    A = Find_Parent(A);
    B = Find_Parent(B);
    if (A == B) return true;
    return false;
}
 
void Solution()
{
    for (int i = 1; i <= N; i++) Parent[i] = i;
    for (int i = 0; i < M; i++)
    {
        int N1 = Party[i][0];
        for (int j = 1; j < Party[i].size(); j++)
        {
            int N2 = Party[i][j];
            Union(N1, N2);
        }
    }
 
    for (int i = 0; i < M; i++)
    {
        bool Go_Party = true;
        for (int j = 0; j < Party[i].size(); j++)
        {
            if (Go_Party == false) break;
            int N1 = Party[i][j];
            for (int k = 0; k < Know_Truth.size(); k++)
            {
                int N2 = Know_Truth[k];
                if (Same_Parent(N1, N2) == true)
                {
                    Go_Party = false;
                    break;
                }
            }
        }
 
        if (Go_Party == false) Answer--;
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}