백준 1043 : 거짓말 (Python)

본문 링크

import sys
input=sys.stdin.readline

N,M=map(int,input().split())

TRUE_PEOPLE=set(map(int,input().split()[1:]))

party=[]

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

dp=[False]*M # 가능한 파티를 체크한다.

for _ in range(M):
    for i,j in enumerate(party):
        if TRUE_PEOPLE&j: # 공통된 부분이 1개이상이라도 있는가?
            dp[i]=True
            TRUE_PEOPLE=TRUE_PEOPLE | j #두 집합을 합한다 - 합집합

print(dp.count(False))

📌 어떻게 접근할 것인가?

원래는 유니온 파인드 문제지만 문제에서 주어지는 입력값의 범위가 작아서 반복문을 여러개 사용해도 시간초과가 나지 않는다.

일단 진실을 아는 사람들의 집합을 입력받고 파티에 참석하는 사람들을 입력받는다.

이후 $M$ 번동안 파티에 대해서 진실을 아는 사람이 한명이상이라도 존재하는 경우
$dp[i]=True$ 로 설정해주고 두 집합을 서로 합해준다.

따라서 모든 파티에 대해서 각각 하나의 파티는 서로다른 모든 파티에서 공통된 부분이 있는지 체크를 해주는 것이다.