[BOJ] 백준 1043 거짓말

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

 Input 

4 3

0

2 1 2

1 3

3 2 3 4

 

 Output 

3

과장된 이야기를 하기위해서는 진실을 아는 사람이 아무도 없어야 합니다.

그렇다고 진실을 아는 사람이 없다고 무조건적으로 과장된 이야기를 하다보면

여러 파티 참석을 거듭하면서 거짓말쟁이로 알려지기 때문에 이러한 경우는 피해야 합니다.

즉, 과장된 이야기를 들은 사람이 추후에 진실된 이야기를 들어서는 안됩니다.

 

진실을 아는자 : {1}

파티 A = {5, 6}

파티 B = {4, 5}

파티 C = {3, 4}

파티 D = {2, 3}

파티 E = {1, 2}

ex) 파티 D에서 과장된 이야기를 했다가 파티 E에서 진실된 이야기를 하게되면,

2번 사람을 통해 거짓말 쟁이가 됩니다. 결과적으로 파티 D에서는 진실된 이야기를 해야하며

3번 사람으로 인해 파티 C에서도 진실을 말해야 합니다.

주어진 Input Data를 분석하면 결과적으로는 모든 파티에서 진실된 이야기를 할 수 밖에 없습니다.

 Input 

6 5

1 1

2 5 6

2 4 5

2 3 4

2 2 3

2 1 2

 

 Output 

0

ⅰ. 파티별 모든 참가자를 탐색

    - 이미 진실을 말하기로 판정된 파티 제외

    - 진실을 알고 있는 참석자가 존재하는 경우

    - 해당 파티는 진실을 이야기 하는 것으로 check

    - 아직 진실을 모르는 참가자도 모두 알게되는 것으로 추가 check

ⅱ. 과정 ⅰ에서 진실을 알게된 사람이 추가로 발생된 경우

     다시한번 과정ⅰ을 수행하면서 진실을 말해야 할 파티를 다시 찾아봅니다.

 

시뮬레이션

- 진실을 아는자 = {1}

파티 A = {5, 6}

파티 B = {4, 5}

파티 C = {3, 4}

파티 D = {2, 3}

파티 E = {1, 2}

 

- 진실을 아는자 = {1, 2}

파티 A = {5, 6}

파티 B = {4, 5}

파티 C = {3, 4}

파티 D = {2, 3}

[T] 파티 E = {1, 2}

 

- 진실을 아는자 = {1, 2, 3}

파티 A = {5, 6}

파티 B = {4, 5}

파티 C = {3, 4}

[T] 파티 D = {2, 3}

[T] 파티 E = {1, 2}

 

- 진실을 아는자 = {1, 2, 3, 4}

파티 A = {5, 6}

파티 B = {4, 5}

[T] 파티 C = {3, 4}

[T] 파티 D = {2, 3}

[T] 파티 E = {1, 2}

 

- 진실을 아는자 = {1, 2, 3, 4, 5}

파티 A = {5, 6}

[T] 파티 B = {4, 5}

[T] 파티 C = {3, 4}

[T] 파티 D = {2, 3}

[T] 파티 E = {1, 2}

 

- 진실을 아는자 = {1, 2, 3, 4, 5, 6}

[T] 파티 A = {5, 6}

[T] 파티 B = {4, 5}

[T] 파티 C = {3, 4}

[T] 파티 D = {2, 3}

[T] 파티 E = {1, 2}

 

추가로 진실을 알게 되는 멤버도 없으며, 더 이상 판단할 파티도 없음

이 중에서 과장된 이야기를 할 수 있는 파티 개수 = 0개

---

#include <iostream>
using namespace std;
#define MAX 51
 
bool isAddTruthMember, isTruthParty[MAX], truthMembers[MAX], party[MAX][MAX];
int temp, N, M, truthMemberCnt, partyGoerCnt;
 
bool findTruthMeber(int p) {
    for (int i = 1; i <= N; i++) {
        // 참석자이면서 진실을 알고있는 멤버인 경우
        if (party[p][i] && truthMembers[i])
            return true;
    }
    return false;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    // 참석자 수, 파티 수
    cin >> N >> M;
 
    // 진실을 아는 사람 수
    cin >> truthMemberCnt;
    for (int i = 1; i <= truthMemberCnt; ++i) {
        cin >> temp;
        truthMembers[temp] = true;
    }
 
    // 파티별 참석자
    for (int i = 1; i <= M; i++) {
        cin >> partyGoerCnt;
        for (int j = 1; j <= partyGoerCnt; j++) {
            cin >> temp;
            party[i][temp] = true;
        }
    }
 
    while (1) {
        isAddTruthMember = false;
 
        // 각 파티를 순회
        for (int i = 1; i <= M; i++) {
            // 이미 진실을 이야기 판정된 파티 제외
            if (isTruthParty[i]) continue;
 
            // 파티 참석자 중 진실을 알고 있는 사람 확인
            if (findTruthMeber(i)) {
                for (int j = 1; j <= N; j++) {
                    // 진실을 알고 있는 참석자가 한 명이라도 있으면
                    // 진실을 몰랐던 다른 참석자도 모두 진실을 알게됩니다.
                    if (party[i][j] && !truthMembers[j]) {
                        truthMembers[j] = true;
                        isAddTruthMember = true;
                    }
                }
                // 해당 파티는 진실을 이야기하는 파티로 확정
                isTruthParty[i] = true;
            }
        }
        // 더 이상 추가로 진실을 알만한 멤버가 생기지 않는 경우
        if (!isAddTruthMember) break;
    }
 
    int answer = 0;
    for (int i = 1; i <= M; i++) {
        if (!isTruthParty[i]) answer++;
    }
    cout << answer << endl;
}