[백준] 1043 거짓말 (파이썬 python)

 

 

문제 링크

---

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

1043번: 거짓말

 

 

문제 풀이

---

 

처음에는 단순히 진실을 아는 사람과 참석 인원 중

교집합이 없는 파티를 구하면 되는 것 아닌가 하고 간단히 생각했습니다.

하지만 그렇게 생각하면 예제 입력 4번부터 출력이 다르게 됩니다.

 

문제에서 주어진 조건은

지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수를 구하는 것이었습니다.

 

만약, 1번 친구가 진실을 모른다고 1번 친구만 있는 파티에서 거짓말을 했다고 가정해봅시다.

다음 파티에서 진실을 아는 친구와 1번 친구가 같이 참석했을 경우,

진실을 아는 친구가 있기 때문에 무조건 진실을 말해야 하는데 그러면 1번 친구에게는 거짓말쟁이가 됩니다.

따라서, 1번 친구만 있는 파티에서도 진실을 말했어야 하는 것이죠

 

이를 해결하기 위해, 진실을 아는 사람과 같은 파티에 가는 사람들을 도출하여

거짓말을 할 수 없는 사람으로 분류하고

참석 인원과 거짓말을 할 수 없는 사람의 교집합이 없는 파티에 대해서만

과장된 이야기를 할 수 있으므로 정답에 1을 추가해줍니다.

 

from collections import deque

# 사람 수 n, 파티 수 m
n, m = map(int, input().split())
# 진실을 아는 사람
know = list(map(int, input().split()))
know.pop(0)
# 각 사람 별 마주친 사람
meet = list({0} for _ in range(n + 1))
party = []

# 파티에 함께 하는 사람들간의 관계를 meet에 저장
for _ in range(m):
    temp = list(map(int, input().split()))
    for i in range(1, temp[0] + 1):
        for j in range(1, temp[0] + 1):
            if i != j:
                meet[temp[i]].add(temp[j])
    party.append(temp)

# 진실을 알고 있는 사람과 함께 파티에 가는 사람들을 know에 저장
# 기존에 진실을 알고 있지 않았더라도, 같이 간 사람으로 인해 know에 저장된 사람들에 대해서도
# 함께 파티에 가는 사람들을 know에 저장
queue = deque(know)
while queue:
    now = queue.popleft()
    for i in (meet[now]):
        if i in know:
            continue
        else:
            know.append(i)
            queue.append(i)

result = 0
for i in range(m):
	# 진실을 알고 있는 사람과 파티 참석 인원의 교집합
    intersection = list(set(know) & set(party[i][1:]))
    if intersection:
        continue
    # 교집합이 없을 경우 (= 진실을 알고 있는 사람이 없을 경우)
    else:
        result += 1

print(result)