이 문제는 파이썬의 집합 자료형을 이용하면 쉽게 풀 수 있는 문제이다. 처음에는 간단하게 생각하여 진실을 아는 사람이 포함되지 않은 파티의 개수를 반환하면 된다고 생각했다. 다시 생각해보니, 진실을 아는 사람이 포함된 파티에 있는 사람들도 진실을 알게 되므로, 진실을 아는 사람과 접점이 있는 모든 사람들을 진실을 아는 사람으로 취급하고 답을 반환해야 한다. 이를 간단하게 하기 위해서 진실을 아는 사람, 파티에 있는 사람을 모두 set() 자료형을 사용하여 선언해야 한다. 그리고 파티를 계속 순회하며 진실을 아는 집합과 파티 집합의 교집합이 존재할 경우에, 진실을 아는 집합을 이 두 집합의 합집합으로 갱신해주는 방식으로 접점이 있는 사람들을 모두 진실을 아는 집합으로 모은다. 그리고 난 후에 파티를 다시 순회하며 진실을 아는 집합과의 교집합이 존재하지 않을 경우에만 카운팅 변수를 증가시켜주고, 카운팅 변수를 출력하여 해결하였다.

• n, m을 입력받는다.
• 진실을 아는 집합 knower를 선언하고 입력받는다.
• 파티 집합을 담을 리스트 parties를 선언한다.
• 결과를 저장할 카운팅 변수 answer를 0으로 선언한다.
• m번 반복하는 for문을 돌린다.
  -> parties에 파티에 참여한 사람들을 집합으로 입력받는다.
• m번 반복하는 for문을 돌린다.
  -> parties를 순회하는 party에 대한 for문을 돌린다.
  --> 만약 party와 knower의 교집합이 존재할 경우,
  ---> knower를 knower과 party의 합집합으로 갱신한다.
• parties를 순회하는 party에 대한 for문을 돌린다.
  -> 만약 party와 knower의 교집합이 존재할 경우, 다음 반복으로 넘긴다.
  -> answer를 1 증가시킨다.
• answer를 출력한다.

Code

n, m=map(int, input().split())
knower=set(input().split()[1:])
parties=[]
answer=0
for _ in range(m):
    parties.append(set(input().split()[1:]))
for _ in range(m):
    for party in parties:
        if party & knower:
            knower=knower.union(party)
for party in parties:
    if party & knower:
        continue
    answer+=1
print(answer)

집합 연산

집합 a, b가 존재한다고 가정하고 집합 연산자를 정리해보았다.

• 교집합 - & or intersection
  - &: a & b
  - intersection: a.intersection(b)
• 합집합 - | or union
  - |: a | b
  - union: a.union(b)
• 차집합 - - or difference
  - a - b
  - a.difference(b)