1043 거짓말

1043 거짓말 (c++)

문제

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

접근 방식

1. 처음엔 아래로 순차접근 하면서 한번씩 진실을 알고 있는 사람이 있는지 확인하고 없다면 answer++ 해줬다.
2. 그랬더니 ‘처음엔 진실을 모르는 사람끼리 있다가 다음에 진신을 알고 있는 사람과 함께있는 사람’이 생겨서 실패했다.

    /*  ex)
        1   3   진실을 알고 있음
        2   1   2   진실을 알고 있지 않은 사람끼리 있음 (거짓말을 함)
        3   1   2   3   진실을 알고 있는 사람과 함께 있음 (거짓말이 발각 됨)
    */ 
   

3. 그래서 다음엔 한번 먼저 쭉 돌면서 체크를 해주고 다음번에 answer를 카운트 해줬음
4. 그랬더니 2번에서 한단계 추가된 상황이 발생함

    /*  ex)
        1   3
        2   1   2   // 하지만 여기서 결국 1ㅇㄹ 피해야 했지만 피하지 못함
        2   1   4   // 두번째로 내려오면서 answer cnt 할 때 4가 포함되어 있다는 걸 알아서 피해갈 수 있음
        2   4   3   // 한번 내려오면서 체크할 때 확인할 수 있음 (4 포함)
   
    */
   

5. 조금만 더 머리를 썼으면 1번 돌릴 때마다 1층씩 피해갈 수 있으므로 m(파티의 수)만큼 돌리면 결국 모든 연쇄를 피해갈 수 있다는걸 눈치 챘어야함 (하지만 난 질문 게시판에서 반례를 찾다가 제목에 스포 당함 ‘왜 꼭 M번 돌아야 하는거죠?’)
6. 결국 파티 명단을 M번 돌면서 ‘진실을 아는 사람들’에 한명이라도 포함되는지 확인 후 포함된다면 그 명단 전부를 다시 넣어줬고, 마지막에 answer cnt 했더니 통과함
7. 하지만 이 문제는 union find 문제라고 함 (서로소 집합간의 연산 문제, 그래프 알고리즘)

문제 풀이

#include <iostream>
using namespace std;

bool Check(bool* truth, int* arr) {
    for (int j = 1; j <= arr[0]; ++j) if (truth[arr[j]]) return true;
    return false;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    bool truth[51] = {};
    int N, M, num, temp, answer = 0;
    int arr[50][50] = {};
    cin >> N >> M >> num;
    while (num-- > 0) {cin >> temp; truth[temp] = true;}
    for (int i = 0; i < M; ++i) {cin >> num; arr[i][0] = num; for (int j = 1; j <= num; ++j) {cin >> temp; arr[i][j] = temp;}}
    for (int k = 0; k < M; ++k) for (int i = 0; i < M; ++i) if (Check(truth, arr[i])) for (int j = 1; j <= arr[i][0]; ++j) truth[arr[i][j]] = true;
    for (int i = 0; i < M; ++i) if (!Check(truth, arr[i])) answer++;
    cout << answer << endl;
}

다시 생각해볼 점

1. 한번 돌때마다 파티 한줄씩 파악이 가능한 규칙성을 왜 눈치채지 못했을까.
2. Union Find 알고리즘에 대해 좀 더 깊히 공부해봐야겠다.