[파이썬]백준 1043 거짓말

링크

백준 1043 거짓말

bfs로 풀 수도 있지만 set() 자료구조를 이용해서 완전탐색을 했다.

진실을 알고 있는 사람집합과 파티에 참여한 사람집합을 만들고
이 둘의 교집합이 생길 경우 해당 파티는 거짓말을 할 수 없으므로
해당 파티는 거짓말을 할 수 없음(ans[idx] = 0) 처리해주고 진실을 아는 사람 집합에 해당 파티의 참가자를 합집합해준다.

중간부터 연계되어서 아는 사람 집합에 추가되지 않은 사람이 있을 수 있으므로 파티의 갯수만큼 반복해 모든 경우를 완전탐색 한다.

정답 코드

import sys; input = sys.stdin.readline

N, M = map(int, input().split())
T = set(input().split()[1:])

parties = []
ans = [1] * M # 다 거짓말을 할 수 있음

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

for _ in range(M):
    for idx, party in enumerate(parties):
        if ans[idx]: # 거짓말 할 수 있는 파티일때만 검증
            if T & party: # 교집합 있으면
                T.update(party) # 진실을 말해야 하는 집합에 추가하고
                ans[idx] = 0 # 해당 번호의 파티를 거짓말 할 수 없음 처리

print(sum(ans))

알게된 것👨‍💻

• set 잘쓰면 진짜 좋은데..