백준 1043 - 거짓말 [Python]

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

1043번: 거짓말

---

풀이 과정

진실을 아는 사람, 진실을 들었던 사람들이 참가한 파티에서는 거짓말을 할 수 없고, 진실을 아는 사람과 파티에 참석하는 사람들의 번호가 주어질 때 거짓말을 할 수 있는 최대 횟수를 구하는 문제이다.

 

문제를 읽고 생각할 수 있는 것은

1. 파티에 진실을 아는 사람이 참석했으면 무조건 진실을 말해야 한다.

2. 진실을 아는 사람이 참석한 파티의 모든 참가자들은 진실을 듣게 되었으므로, 원래 진실을 몰랐던 사람도 아는 사람으로 바뀌게 된다.

 

라고 판단하고 코드를 짠 다음에 예시 입력을 넣어보면 예시 출력과 다른 답이 나오게 된다. 무엇이 문제일까?

 

1번이라는 사람이 진실을 알고, 첫 번째 파티에 3번이 참가, 두 번째 파티에 1번과 3번이 참가했다고 가정해보자. 첫 번째 파티는 진실을 모르는 3번이 참가했으니 거짓말 횟수 1 증가... 두 번째 파티는 진실을 아는 1번이 참가했으니 3번을 진실을 아는 사람으로 설정하고 거짓말 횟수 보류... 이러면 오답을 출력하게 된다. 최종적으로는 3번이 진실을 알게 되므로 첫 번째 파티에서 거짓말을 하면 3번에게 거짓이라는 것을 2번째 파티에서 들키게 된다.

 

파티 참가자들을 살펴보며 union-find를 사용해서 진실을 아는 사람, 진실을 들은 사람을 전부 다 연결시키고, 다시 한번 파티 참가자들을 살펴보면서 진실을 모르는 사람들만 있는 파티에서 거짓말 횟수를 증가시키면 문제를 해결할 수 있다.

---

소스 코드

import sys

parent = [i for i in range(51)]
truth_check = [False for _ in range(51)]


def find(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]


def uni(a, b):
    aRoot = find(a)
    bRoot = find(b)
    if aRoot == bRoot:
        return
    if truth_check[aRoot]:
        parent[bRoot] = aRoot
        return

    parent[aRoot] = bRoot


N, M = map(int, sys.stdin.readline().split())
truth_people = list(map(int, sys.stdin.readline().split()))
people_list = []

if truth_people[0] != 0:
    for i in range(1, truth_people[0] + 1):
        truth_check[truth_people[i]] = True

for _ in range(M):
    people = list(map(int, sys.stdin.readline().split()))
    people_list.append(people[1:])
    prev = people[1]

    for i in range(1, people[0] + 1):
        uni(prev, people[i])
        prev = people[i]

answer = 0

for peo in people_list:
    truth_flag = False
    for pe in peo:
        if truth_check[find(pe)]:
            truth_flag = True
    if not truth_flag:
        answer += 1

print(answer)