[백준 BOJ_1043] 거짓말 Python 풀이

출처: 백준 온라인 저지

문제

풀이

우선 비밀을 알고 있는 사람의 번호들을 set으로 저장해줍니다.

모든 파티의 멤버들 또한 set으로 저장하여 parties라는 list에 추가해줍니다.

파티의 멤버에 비밀을 알고 있는 사람이 포함된다면 그 파티 멤버를 truth(비밀을 아는 멤버의 set)에 추가해줍니다. 이때, 새로운 사람이 truth에 추가될 때마다 다시 한번 새로운 사람이 다른 사람과 파티를 하지 않는 지 체크해주어야 하는 데 최악의 경우는 다음과 같이 매번 체크해줄 때마다 다른 파티에서 갱신될 때입니다.

6 5 (사람의 수, 파티의 수)
1 1 (비밀을 아는 사람의 수, 비밀을 아는 사람의 번호)
2 1 2 (파티에 참여하는 사람의 수, 파티에 참여하는 사람의 번호)
2 2 3
2 3 4
2 4 5
2 5 6

• 총 5번의 파티에서 1번 파티에 비밀을 아는 사람이 있었다.
• 1번 파티에 참여한 사람들은 모두 truth에 추가된다.
• 2번 사람은 2번 파티에도 참가한다.
• 2번 파티에 참여한 사람들도 모두 truth에 추가된다.

이런 식으로 5번까지 이어진다면 결국 5번을 체크해주어야 합니다. 다른 말로, 우리는 결국 모든 파티의 구성원들을 추가해주어야 하므로 파티의 수만큼 반복하게 됩니다.

그래서 M만큼 체크해주고 난 뒤 파티를 다시한번 돌아주며 truth와 겹치는 멤버가 있을 경우 M으로 초기화해준 result에서 1씩 감소시켜줍니다.

코드

N, M = map(int,input().split())
truth = set(list(map(int, input().split()))[1:])
result = M
parties = []

for _ in range(M):
  members = set(list(map(int, input().split()))[1:])
  parties.append(members)

for _ in range(M):
  for party in parties:
    if party & truth:
      truth = truth | party

for party in parties:
  if party & truth:
    result -= 1

print(result)