[백준][Python] 1043번 거짓말

1043번: 거짓말

 

코드

n,m = map(int,input().split())
know = set(map(int,input().split()[1:]))
party = []
for _ in range(m):
	party.append(set(map(int,input().split()[1:])))

for _ in range(m):
	for p in party:
		if p & know:
			know = know | p
ans = 0
for p in party:
	if not p & know:
		ans += 1

print(ans)

 

설명

p & know (교집합) 이 존재하는 경우 진실을 아는 사람이 포함되었다는 뜻이기 때문에 p 집합에 있는 사람을 모두 know에 넣어줘야 한다.

파티의 수 만큼 위의 과정을 반복을 해줬는데 그 이유는

예를 들어 1만 진실을 알고 있고 

2 2 3   

2 1 2

가 순서대로 들어온 경우 처음으로 위 과정을 진행하면 know에 {1,2} 만 들어오게 된다. 따라서 다시 한번 진행을 해야 3도 know에 들어올 수 있다.