[백준 1043] 거짓말

문제

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

1043번: 거짓말

---

아이디어

진실을 아는 사람들의 번호를 n_know_lst 라는 리스트에 저장한다. 

이 때, 처음에는 진실을 아는 사람이라고 했지만, 다른 말로 하면 거짓말을 칠 수 없는 사람들이기도 하다. 

왜 이렇게 표현했냐면, n_know_lst에 속하는 사람과 같은 파티에 있었던 사람에게는 거짓말을 칠 수 없게 되는 것이다. 

즉, 모든 파티를 순회하면서 n_know_lst 의 정보를 이용해서, n_know_lst에 속하는 사람과 같은 파티장에 있었던 사람들까지도 n_know_lst 에 추가하는 것이다. 

 

그러면 최종적으로 내가 거짓말을 칠 수 없는 사람들의 리스트를 얻을 수 있게 된다. 

그리고 다시 모든 파티를 순회하면서, 그 파티에 있는 사람들 중 n_know_lst 에 속하는 사람이 단 한 명도 없을 때, 그 파티에서 거짓말을 칠 수 있게 된다. 

 

예제 입력 4를 좀 더 변형해서 예시를 들어보자.

4 6
1 1
1 1
1 2
1 3
1 4
2 4 1
2 4 2

총 4명이 있고, 파티는 6번 열린다. 이 때, 진실을 아는 사람(즉, 거짓말을 치면 안 되는 사람)은 1번 사람 1명 뿐이다. 

각 파티에 대해서 하나씩 살펴보자. (n_know_lst와 함께)

1. 1번 사람 1명만 온다. 

> 당연히 거짓말을 칠 수 없다. n_know_lst = [ 1 ]

2. 2번 사람 1명만 온다. 

> 거짓말을 칠 수 있다. n_know_lst = [ 1 ]

 

3. 3번 사람 1명만 온다. 

> 거짓말을 칠 수 있다. n_know_lst = [ 1 ]

4. 4번 사람 1명만 온다.

> 거짓말을 칠 수 있다. n_know_lst = [ 1 ]

여기까진 문제가 없다. 

5. 1번 사람과 4번 사람, 2명이 온다. 

> 1번 사람 때문에 거짓말을 칠 수 없다. 그런데, 아까 4번 사람한테 거짓말을 쳤었다.

> 따라서 4번한테 거짓말을 치면 안 된다. n_know_lst = [ 1, 4 ]

6. 2번 사람과 4번 사람, 2명이 온다. 

> 4번 사람이 추가되는 바람에 거짓말을 칠 수 없다. 그런데 아까 2번 사람한테 거짓말을 쳤었다.

> 따라서 2번한테도 거짓말을 치면 안 된다. n_know_lst = [ 1, 2, 4 ]

 

결론은, 3번 사람만 있는 파티에서만 거짓말을 칠 수 있다. 

하지만 이 풀이를 이용하면 다음과 같은 경우를 놓치게 된다. 

4 4
1 1
2 5 4 
2 4 3 
2 3 2 
2 2 1

총 4명이 있고, 파티는 4번 열린다. 이 때, 진실을 아는 사람(즉, 거짓말을 치면 안 되는 사람)은 1번 사람 1명 뿐이다. 

각 파티에 대해서 하나씩 살펴보자. (n_know_lst와 함께)

1. 5번 사람과 4번 사람, 2명이 온다. 

> 거짓말을 칠 수 있다. n_know_lst = [ 1 ]

2. 4번 사람과 3번 사람, 2명이 온다. 

> 거짓말을 칠 수 있다. n_know_lst = [ 1 ]

3. 3번 사람과 2번 사람, 2명이 온다. 

> 거짓말을 칠 수 있다. n_know_lst = [ 1 ]

4. 2번 사람과 1번 사람, 2명이 온다. 

> 거짓말을 칠 수 없다. n_know_lst = [ 1, 2 ]

그러면 우리가 얻을 수 있는 결론은, 1번 사람과 2번 사람만 피하면 된다. 하지만 그렇지 않다. 

2번 사람에게 거짓말을 칠 수 없기 때문에 3번 사람에게 거짓말을 칠 수 없게 되고,

3번 사람에게 거짓말을 칠 수 없기 때문에 4번 사람에게 거짓말을 칠 수 없게 되고,

4번 사람에게 거짓말을 칠 수 없기 때문에 5번 사람에게 거짓말을 칠 수 없게 된다. 

 

파티 배열에 따라서 최악의 경우 이런 문제가 생길 수 있게 되는 것이다. 

해결책은 간단하다. 다음 과정을 파티의 수만큼만 반복하면 거꾸로 돌아가는 과정까지 잡아낼 수 있다. 

 

위의 예시에서 n_know_lst의 변화를 [ 1 ] -> [ 1 ] -> [ 1 ] -> [ 1, 2 ]라고 표현하고, 이 과정을 파티의 수 M ( = 4)로 나타내면

iter 1 :  [ 1 ] -> [ 1 ] -> [ 1 ] -> [ 1, 2 ] (위의 예시)

iter 2 :  [ 1, 2 ] -> [ 1, 2 ] -> [ 1, 2, 3 ] -> [ 1, 2, 3 ] 

iter 3 :  [ 1, 2, 3 ] -> [ 1, 2, 3, 4 ] -> [ 1, 2, 3, 4 ] -> [ 1, 2, 3, 4 ] 

iter 4 :  [ 1, 2, 3, 4, 5 ] -> [ 1, 2, 3, 4, 5 ] -> [ 1, 2, 3, 4, 5 ] -> [ 1, 2, 3, 4, 5 ] 

가 되면서, 모든 경우를 다 찾아낼 수 있다. 

그런데, 좀 무식한 방법인 것 같다. 유니온 파인드를 이용해서 푸는 방법도 새로 올려보려고 한다.

 

---

Solution

N, M = map(int, input().split())
knows = input()
if knows == '0' : 
    n_know, n_know_lst = 0, [0]
else : 
    n_know, n_know_lst = int(knows[:1]), list(map(int, knows[1:].split()))

party = {} 

for _ in range(M):
    p = list(map(int, input().split()[1:]))
    party[_] = p

for _ in range(M):
    for key, values in party.items():
        if len(set(values).intersection(set(n_know_lst))) > 0:
            n_know_lst.extend(values)
            n_know_lst = list(set(n_know_lst))

answer = 0 
for key, value in party.items() : 
    if len(set(value).intersection(n_know_lst)) == 0 : 
        answer += 1 

print(answer)