[Python/파이썬] 백준 1043번: 거짓말

문제

 

풀이

진실을 알고 있는 사람의 집합을 knowList

파티에 참석한 사람의 집합을 party

party를 원소로 갖는 배열 parties

 

1.

만약 party, knowList의 교집합이 하나라도 있으면 knowList = knowList.union(party)

(파티에 진실을 아는 사람이 한 명이라도 있다면, 그 사람으로 인해 파티에 참석한 모든 사람이 진실을 알게 됨)

 

2.

위 과정을 파티의 수만큼 반복

 

why??

5개의 파티가 있고 진실을 아는 사람이 A라고 가정하자.

이 경우 5개의 파티 중 A가 참여한 파티가 있는지 확인하면 된다.

확인하던 도중 A가 3번째 파티에 참여한 것이 발견되어 B 역시 진실을 알게 되었다고 가정하자.

 

B에 대해서도 마찬가지로 5개의 파티 중 B가 참여한 파티가 있는지 확인해야 한다.

이때 새로운 사람이 진실이 알게 되는 경우의 최대 값은 매 파티마다 진실을 알게 되는 사람이 생기는 것이다.

따라서 파티의 수만큼 반복해야 한다.

 

코드

import sys
input = sys.stdin.readline

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

for _ in range(m):
    parties.append(set(input().split()[1:]))

for _ in range(m):
    for party in parties:
        if party & knowList:
            knowList = knowList.union(party)

cnt = 0
for party in parties:
    if party & knowList:
        continue
    cnt += 1

print(cnt)

 

마무리

풀이를 보니 쉬운데... 왜 이걸 생각 못했을까 싶다.

해답을 보고도 쉽게 이해하지 못했다.

아직 많이 부족하다. 언제쯤 잘할 수 있을까 ㅠㅠ