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

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

1043번: 거짓말

문제 요약 : 사람 수 N과 파티 수 M, 진실을 아는 사람수와 번호, 각 파티에 오는 사람의 수와 번호가 주어진다. 진실을 아는 사람에게는 과장된 말을 할 수 없다. 또한, 진실된 말과 과장된 말 둘 다 듣는 사람도 있을 수없다. 지민이가 진실을 말할 수 있는 파티의 수의 최댓값을 출력하라.

 

예제 입력1

4 3
0
2 1 2
1 3
3 2 3 4

예제 출력1

3

 

📌 풀이 )

queue를 이용하여 풀었다.

know : 진실을 아는사람 혹은 진실을 말해야하는 파티에 참가하는 사람

meet : 파티에서 만나는 사람들(ex. meet[1]의 값들은 1번 사람이 만나는 사람들을 의미)

 

먼저 진실을 아는 사람의 수는 필요없어서 know.pop(0)을 해주었다.

 

party에 참여하는 사람에 대한 정보를 임의로 tmp로 받아온다.

그리고 meet에 각각 만나는 사람의 정보를 넣어준다.

party에 tmp를 추가해준다.

 

queue에 진실을 아는 사람을 추가해준다.

queue.popleft()를 한다.

만일, 그 사람이 만난 사람이 know에 들어있지 않으면, 추가해주고 queue에도 추가한다.

queue가 없을 때 까지 반복한다.

 

파티를 돌면서 해당 파티에 참가하는 사람과 know 사이의 교집합을 확인한다.

만일, 교집합이 존재하지 않으면 answer에 + 1을 해준다.

 

answer을 출력한다.

# 거짓말
from collections import deque

N, M = map(int,input().split())
know = list(map(int,input().split()))
meet = list({0} for _ in range(N+1))
party = []

know.pop(0)

for i in range(M):
    tmp = list(map(int,input().split()))
    for i in range(1,tmp[0]+1):
        for j in range(1,tmp[0]+1):
            meet[tmp[i]].add(tmp[j])
    party.append(tmp)

queue = deque(know)
while queue:
    tmp = queue.popleft()
    for i in (meet[tmp]):
        if i in know :
            continue
        else :
            know.append(i)
            queue.append(i)
        

answer = 0
for i in range(M):
    intersection = list(set(know) & set(party[i][1:]))
    if intersection :
        continue
    else :
        answer += 1

print(answer)