[Python] 거짓말 - 백준

해당 글은 백준 1043번 문제 '거짓말'을 다룬다.

문제

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

1043번: 거짓말

 

설명

해당 문제는 집합으로 교집합과 합집합을 통해 쉽게 해결할 수 있다.

주의할 점은 진실을 아는 사람들의 집합이 업데이트 되면, 이전의 파티에 왔던 사람들도 다시 검사를 해줘야한다.

즉, 2중 for문으로 전체를 다시 검사하여 최종 진실을 아는 사람들의 집합을 만들어줘야한다.

 

코드

n, m = map(int, input().split())
true_people = set(list(map(int, input().split()))[1:])

party = []
for i in range(m):
    party_people = set(list(map(int, input().split()))[1:])
    party.append(party_people)

for _ in range(m):
    for p in party:
        if len(true_people.intersection(p)):
            true_people = true_people.union(p)

result = 0
for p in party:
    if not len(true_people.intersection(p)):
        result += 1
print(result)