본문 바로가기

백준/골드

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

문제링크 : https://www.acmicpc.net/problem/1043

 

1043번: 거짓말

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게

www.acmicpc.net

 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N, M, K;
int parent[51];  //진실을 아는 사람의 수
vector<int>know;
vector<int>party[50]; //파티 오는 사람 수

int find_root(int x)
{
    if(x == parent[x]) return x;  //루트노드면 그대로 반환
    return x = find_root(parent[x]);  //자식노드면 부모노드로 다시 탐색
}

void Union(int a, int b)
{
    a = find_root(a);
    b = find_root(b);
    if(a!=b)
    {
        parent[a]=b;  //속한 트리가 다르다면 병합시킴 (Union)
    }
}

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

    cin >> N >> M >> K;

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

    for(int i=0; i<K; i++)
    {
        int n_know;
        cin >> n_know;
        know.push_back(n_know);  //진실을 아는 사람들
    }
    
    for(int i=0; i<M; i++)
    {
        int P, num;              //파티 참여 인원과 번호
        cin >> P;
        for(int j=0; j<P; j++)
        {
            cin >> num;
            if(j>=1)
            {
                Union(party[i][j-1], num); //이전 값과 연결
            }
            party[i].push_back(num);
        }
    }

    int result = M;

    for(int i=0; i<M; i++)  // 파티 수
    {
        bool flag = false;
        for(int j=0; j<party[i].size(); j++)  //파티당 인원수 
        {
            if(flag) break; //해당 파티에 진실을 아는 사람이 있다면
            for(int k=0; k<know.size(); k++)  //진실을 아는 사람 수
            {
                if(find_root(party[i][j]) == find_root(know[k])) //파티에 진실을 아는 사람이 있다면
                {
                    flag = true;
                    break;
                }
            }
        }
        if(flag) result --;
    }

    cout << result <<'\n';
    return 0;

}

분리집합 문제이다.

파티에 참여한 인원끼리 묶어주고 난 이후에, 해당 파티에 진실을 아는 사람이 있는지 없는지를 확인한다.

 

파티 참여 인원과 번호를 입력받을 때 크기가 2이상인 것은 유니온을 시켜준다.

이는 진실을 아는 사람이 해당 그룹에 있을 때, 다른 인원들도 진실을 알게되기 때문이다.

진실을 모르던 인원들도 진실을 알게 되어 새롭게 진실을 알게된 인원들한테도 거짓말을 치면 안되기 때문에 체크를 해줘야 한다.

'백준 > 골드' 카테고리의 다른 글

[백준 2513번] 통학버스 (C++)  (0) 2023.04.23
[백준 17144번] 미세먼지 안녕! (C++)  (0) 2023.04.20
[백준 1865번] 웜홀 (C++)  (0) 2023.04.17
[백준 12996번] Acka (C++)  (0) 2023.04.15
[백준 9019번] DSLR (C++)  (0) 2023.04.14