[백준] 1043. 거짓말 (Python)

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

1043번: 거짓말

❗ 주목한 점

✏️ 진실을 알게 된 사람과 같은 파티에 가면 진실을 알게 된다

✏️ 1이 진실을 알고 있는 사람이고, 1과 4가 같은 파티에 간 경우, 4가 참여한 모든 파티가 거짓말을 할 수 없는 파티가 된다.

 

1️⃣ 3% 대에서 오답난 코드

import sys
input = sys.stdin.readline

def knowTruth(y):
    for idx in range(1, len(party[y])):
        check[party[y][idx]] = 1 # 진실을 알고 있으므로 체크

N, M = map(int, input().split()) # 사람의 수, 파티의 수
truth = list(map(int, input().split())) # 진실을 알고 있는 사람의 수 + 번호
truthNum = truth.pop(0) # 진실을 알고 있는 사람의 수
check = [0] * (N+1) # 진실을 알고 있는지 체크
party = [0]*M # 파티
res = 0

for t in truth: # 최초의 진실을 알고 있는 사람 체크
    check[t] = 1

for idx in range(M):
    party[idx] = list(map(int, input().split()))

for y in range(M):
    for x in range(1, len(party[y])):
        if check[party[y][x]]:
            knowTruth(y) # 진실을 아는 사람이 참가한 파티 => 참여자 모두가 진실을 알게 됨

for y in range(M-1, -1, -1):
    for x in range(1, len(party[y])):
        if check[party[y][x]]:
            knowTruth(y) # 진실을 아는 사람이 참가한 파티 => 참여자 모두가 진실을 알게 됨


for y in range(M):
    temp = 0
    for x in range(1, len(party[y])):
        temp += check[party[y][x]] # 진실을 알고 있으면 +1
    if temp == 0: # temp가 0이면 진실을 아는 사람이 없다는 뜻
        res += 1 # 거짓말 할 수 있는 파티 +1

print(res)

- 중간에 진실을 알게 된 경우, 해당 사람이 포함된 모든 파티를 거짓말 할 수 없는 파티로 체크해야 한다.

- 그러나 위 코드로는 파티 리스트를 앞에서부터 한 번, 뒤에서부터 한 번 딱 2번 체크하므로 충분히 모든 경우를 체크하지 못했다.

 

2️⃣ 통과한 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split()) # 사람의 수, 파티의 수
truth = list(map(int, input().split()))[1:] # 진실을 알고 있는 사람들의 번호 리스트
check = [0] * (N+1) # 진실을 알고 있는지 체크
party = [0]*M
party_check = [1]*M # 거짓말 할 수 있는 파티인지 체크

for t in truth: # 최초의 진실을 알고 있는 사람 체크
    check[t] = 1

for idx in range(M):
    party[idx] = list(map(int, input().split()))[1:] # 파티 순서대로 입력

while truth:
    truth_person = truth.pop()

    dontKnow = set() # 진실을 아직 모르는 사람들

    for idx in range(M):
        if truth_person in party[idx]: # 파티에 진실을 알고 있는 사람이 있으면
            party_check[idx] = 0 # 거짓말 할 수 없으므로 체크 해제
            dontKnow = dontKnow.union(party[idx]) # 진실을 아직 모르는 사람들에 파티원들 추가

    for person in dontKnow:
        if not check[person]: # 아직 진실을 모르면
            truth.append(person) # 진실을 알게 되었으므로 truth 리스트에 추가
            check[person] = 1 # 체크

print(sum(party_check))

- 구글링해본 결과, 진실을 알게 될 때마다 그 사람의 번호를 truth 리스트에 담아주었고, while문을 통해 모든 경우를 체크해주었다.

- party_check 리스트에 모든 파티를 거짓말할 수 있는 것(1)로 체크해두고, 거짓말 할 수 없다고 밝혀지는 순간 0으로 값을 바꿔주었다.

- 마지막에 party_check 리스트의 합을 구하면 거짓말할 수 있는 파티의 갯수가 나온다.