[BOJ][python] 1043. 거짓말

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

1043번: 거짓말

---

💡IDEA

집합을 사용하는 문제이다.

진실을 아는 사람과 파티에 포함된 사람을 집합으로 만들어준다.

진실을 아는 사람이 포함된 파티에 있는 모든 사람을 진실을 아는 사람으로 취급해야한다. 즉, 교집합으로 찾으면서 진실을 아는 사람 집합을 업데이트 한다.

갱신한 진실을 아는 사람 집합과 파티에 있는 사람 집합을 다시 교집합 했을 때 겹치는 부분이 없다면 카운트 센다.

 

📌CODE

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
fact_nums = set(list(map(int, input().split()))[1:])

parties = []
for _ in range(M):
    parties.append(set(list(map(int, input().split()))[1:]))

for _ in range(M):
    for party in parties:
        if party & fact_nums:
            fact_nums = fact_nums.union(party)
            
ans = 0
for party in parties:
    if party & fact_nums:
        continue
    ans += 1
print(ans)