백준 1043 거짓말 c++ [컴공과고씨]

https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

문제 간단 정리

지민이가 여러 개의 파티에 감.

파티마다 참석하는 사람이 주어짐.

지민이가 거짓말을 할 건데 진실을 아는 사람이 주어짐.

진실을 아는 사람에게 거짓말을 하면 안됨. 또한 어느 파티에서는 거짓을 듣고 다른 파티에서 진실을 듣는 것도 안됨.

즉, 거짓말이라는 것을 아무도 알아채지 못하게 거짓말을 많이 할 수 있는 파티의 개수를 구하라.

 

문제 해결 방법

이 문제 같은 경우 유니온 파인드를 쓰면 쉽게 풀 수 있다. 

유니온 파인드를 모를 경우 https://hagisilecoding.tistory.com/122 여기서 보시고 오면 된다. 

간단히 말하면 같은 부류끼리 분류를 해주는 것이다.

 

일단 사람들은 자신의 사람 번호로 그룹으로 분류해준다. 

그 다음 진실을 아는 사람은 그룹 0번으로 분류를 해준다.

 

그 후 첫번째 온 사람 기준으로 그룹을 합쳐 주는데

그룹을 합칠 때 0번 그룹이 진실을 아는 사람이기 때문에 더 작은 그룹으로 합쳐주어야 한다.

이렇게 하면 진실을 아는 그룹과 모르는 그룹으로 나누어지게 되고

그 후 각 파티에 진실을 아는 사람이 있을 경우 거짓말을 하지 못하는 파티의 수를 셀 수 있다.

 

전체 코드

#include <iostream>
using namespace std;
// 자신의 그룹이 어디에 속해있는지 리턴
int find_p(int parent[], int x){
    if(x != parent[x])
        return parent[x] = find_p(parent, parent[x]);
    else
        return parent[x];
}
// x와 y를 같은 그룹으로 만들어줌
void mer(int parent[], int x, int y){
    int px = find_p(parent, parent[x]);
    int py = find_p(parent, parent[y]);
    if(px != py){
        if(px < py)
            parent[py] = parent[px];
        else
            parent[px] = parent[py];
    }
}
int main(){
    int n,m; // 사람 수, 파티 수
    cin >> n >> m;
 
    int know_tru; // 진실을 아는 사람 수
    cin >> know_tru; 
    
    int parent[53]; // 어느 그룹에 속해 있는지 
    
    for(int i =0;i<=n; i++)
        parent[i] = i; // 각자 자신의 그룹으로 먼저 분류
    
    int temp; // 진실을 아는 사람
    for(int i =0 ;i<know_tru;i++){
        cin >> temp;
        parent[temp] = 0; // 진실을 아는 사람은 0 집합으로 분류
    }
 
    int Pnum;
    int temp2;
 
    int arr[53][53]; // 파티번호, 파티 사람 번호
    int arrsiz[53]; // 각 파티의 인원수 저장
    for(int i =0;i<m;i++){
        cin >> Pnum; // 파티에 오는 사람 수 
        cin >> temp; // 파티에 오는 첫번째 사람
        arrsiz[i] = Pnum; // 각 파티의 인원 수 저장
        arr[i][0] =temp; 
        // 첫번째 사람만 올 경우 혼자 오는 것이기 때문에
        // 다른 사람과 그룹을 합치지 않아도 돼서 분류
        for(int j = 1; j < Pnum; j++){
            cin >> temp2; // 파티에 오는 사람 번호
            arr[i][j] = temp2; // 파티에 오는 사람 번호 저장
            mer(parent, temp ,temp2); // 파티에 오는 사람 그룹 합침
        }
    }
    int answer = m; // 전부 거짓말을 할 경우 수 부터 시작
    
    // 각 파티마다 진실을 아는 사람이 한명이라도 있으면 거짓말을 할 수 없음
    // -> 하나 빼줌
    for(int i =0; i<m;i++){
        for(int j=0;j<arrsiz[i]; j++){
            if(find_p(parent, parent[arr[i][j]]) == 0){
                answer--;
                break;
            }
        }
    }
    cout << answer;
    return 0;
}