[백준 / 1043] 거짓말 - Python

https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

<풀이>

파티 순서는 상관이 없다. 왜냐하면 거짓과 진실을 둘다 들을 수 없기 때문이다. 따라서 전염병 같이 진실을 알고 있는 사람과 만난사람, 그 만난 사람과 만난 사람들 모두 체크해서 해당 사람들이 들어간 파티를 제외하면 거짓말을 할 수 있는 파티가 된다.

 

따라서 n번 사람이 접촉하는 사람을 딕셔너리 형태로 만든 후, n번이 접촉한 사람 리스트를 queue에 넣어 이를 반복해서 접촉 리스트를 만든다.

 

from collections import deque

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

truth = list(map(int, input().split()))
truthPeople = truth[1:]

meets = {}
parties = []

for _ in range(M):
    party = list(map(int, input().split()))
    for i in range(party[0]):
        idx = i+1
        now = party[idx]
        if now not in meets:
            meets[now] = party[1:idx]+party[idx+1:]
        else:
            meets[now].extend(party[1:idx]+party[idx+1:])
    parties.append(party)

answer = 0

for i in meets:
    meets[i] = set(meets[i])

queue = deque(truthPeople)
while queue:
    truthPerson = queue.pop()
    if truthPerson in meets:
        gap = list(meets[truthPerson]-set(truthPeople))
        truthPeople.extend(gap)
        queue.extend(gap)

for party in parties:
    if len(set(truthPeople) & set(party[1:])) == 0:
        answer += 1

print(answer)