[CLASS 4]백준 1043번 - 거짓말

1043번 - 거짓말

 

좀 헷갈릴 수 있는 문제이다. 실제로 나도 처음에 막 풀다가 시행착오를 많이 겪었다. 정답 비율이 낮은 것도 이정도면 맞겠지 라고 생각하고 제출한 사람들이 많아서 그런게 아닐까 싶다.

 

집합을 주로 사용해서 푸는 문제는 처음인거 같은데 파이썬의 교집합, 차집합 등이 특정 상황에서 아주 유용하게 쓸 수 있을 것 같다.

 

# dawitblog.tistory.com/149
from sys import stdin
from collections import deque
input = stdin.readline

n, m = map(int,input().split())
l = list(map(int,input().split()))
if l[0]:
    s = set(l[1:])
else:
    print(m)
    exit()

q = deque()
pl = []
# 빈 파티 수
empty = 0
for _ in range(m):
    li = input().split()
    # 파티에 아무도 오지 않는다면
    if li[0] == '0':
        empty += 1
        continue

    t = set(map(int,li[1:]))

    if not s & t:
        pl.append(t)
    else:
        q.append(t-s)

while q:
    t = q.popleft()
    temp = []
    for party in pl:
        if not party & t:
            temp.append(party)
        else:
            q.append(party-t)
    pl = temp

print(len(pl)+empty)

 

이 문제를 풀기 위해서는 그룹을 묶어야 한다. 일단 처음에 진실을 알고 있는 사람의 집합을 만든다.

 

그 뒤 입력을 받으면서 그 집합과 입력받은 집합의 교집합이 하나라도 존재한다면(진실을 아는 사람이 한 명이라도 포함되어 있다면) 그 파티에서는 진실을 말해야 한다. 따라서 차집합을 큐에 저장한다. 이 차집합에 저장된 사람들은 진실을 듣게 될 새로운 사람들이다.

 

이후 큐에서 하나씩 꺼내면서 같은 작업을 큐가 빌 때까지 반복하면 된다. 그러면 결국 pl에는 거짓말을 할 수 있는 파티만 남게 된다. 아무도 안오는 파티에서는 그냥 거짓말을 말해도 되므로 empty 에 1  추가해주고 마지막에 더해주면 된다.