BOJ_1043

오랜만에 풀어보는 분리집합 알고리즘이다. 항상 Find 부분 작성이 헷갈려서 인터넷을 빌리고는 한다..🥲

💻 접근

• 쉽게 말해서 편먹기?? 편가르기?? 그런 느낌이다.
• 어떤 느낌인지는 알겠는데 코드를 구현함에 있어서 생각보다 어려운 문제였다.
• 진실을 알고 있는 사람은 연쇄적이다.
  • 진실을 알고 있는 사람이 A이고
  • 파티 1 : A, B 파티 2 : B, C 파티 3 : C, D 일때
  • 그 어떤 파티에서도 거짓말을 할 수 없게된다.(연쇄작용)
• 파티에 참여하는 모든 사람들에 대한 입력을 받고 순서대로 Uion을 진행하면 될 것이라 판단하고 그렇게 풀어봤다.

💻 입력

    cin >> N >> M;

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

    cin >> truePerson;
    for (int i = 0; i < truePerson; i++)
    {
        int num;
        cin >> num;
        truth.push_back(num);
    }
    for (int i = 0; i < M; i++)
    {
        int num;
        cin >> num;
        for (int j = 0; j < num; j++)
        {
            int person;
            cin >> person;
            v[i].push_back(person);
        }
    }
    

• truth는 진실을 알고 있는 사람의 벡터
• v는 각 파티에 대한 사람들의 벡터

💻 각 파티 사람들과의 Uion 작업

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

💻 판단하는 작업

        for (int i = 0; i < M; i++)
        {
            bool tag = true;
            for (int j = 0; j < v[i].size(); j++)
            {
                for (int k = 0; k < truth.size(); k++)
                {
                    if(find(truth[k]) == find(v[i][j]))
                    {
                        tag = false;
                        break;
                    }
                    if(tag == false)
                        break;
                }
            }
            if (tag == true)
                result++;
        }

• 만약 진실을 알고 있는 사람의 최상위 노드와 v[i][j]의 최상위 노드가 같다면 그 파티에서는 거짓말을 할 수 없게된다. 그렇기에 break;

💻 전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string.h>
#include <set>

using namespace std;

#define endl "\n"

int parent[51];
vector<int> v[51];
vector<int> truth;
bool check[51];

int find(int node)
{
    if(parent[node]==node)
        return node;
    else
        return find(parent[node]);
}

void Union(int a, int b)
{
    a = find(a);
    b = find(b);
    parent[a] = b;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M, truePerson, result = 0;

    cin >> N >> M;

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

    cin >> truePerson;
    for (int i = 0; i < truePerson; i++)
    {
        int num;
        cin >> num;
        truth.push_back(num);
    }
    for (int i = 0; i < M; i++)
    {
        int num;
        cin >> num;
        for (int j = 0; j < num; j++)
        {
            int person;
            cin >> person;
            v[i].push_back(person);
        }
    }
    for (int i = 0; i < M;i++)
    {
        int N1 = v[i][0];
        for (int j = 1; j < v[i].size(); j++)
        {
            int N2 = v[i][j];
            Union(N1, N2);
        }
    }
        for (int i = 0; i < M; i++)
        {
            bool tag = true;
            for (int j = 0; j < v[i].size(); j++)
            {
                for (int k = 0; k < truth.size(); k++)
                {
                    if(find(truth[k]) == find(v[i][j]))
                    {
                        tag = false;
                        break;
                    }
                    if(tag == false)
                        break;
                }
            }
            if (tag == true)
                result++;
        }
    cout << result << endl;
}

✌️ 나름 오랜만에 풀어보는 분리집합 알고리즘이다. 역시 재미있다.