[파이썬]백준 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 잘쓰면 진짜 좋은데..
Author And Source
이 문제에 관하여([파이썬]백준 1043 거짓말), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jajubal/파이썬백준-1043-거짓말저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)