[Python] 백준 / gold / 1043 : 거짓말

분리 집합 문제는 개념을 정확히 이해하고 있지 않으면, 실수하거나 반례가 생기는 로직을 짜기 쉽다. Union-Find 메서드를 작성해서 문제를 풀었다.

먼저, 진실을 알고 있는 사람들을 knownList 에 담고, 서로 Union 한다.
그리고 1~M 개의 파티가 열리는데, 각 파티에 모인 사람들은 모두 같은 집합으로 묶어줘야 된다. 그래야 진실과 거짓을 같이 공유하는 사이로 간주할 수 있게된다.

이 문제에서 가장 좋은 반례는 https://www.acmicpc.net/board/view/85017 에 나오는 반례다.

진실을 아는 사람은 1번 사람. 파티가 4번 열리고, 각 파티에 오는 사람들의 번호가 다음과 같다.
1 2 3
4 5 6
6 7 8
3 8

얼핏 보면 첫번째 파티를 제외하고는 모두 거짓말을 해도 될 것 같다.
하지만 마지막 파티를 보면 3과 8이 공존한다. 3은 첫 번째 파티에서 1과 함께 있던 사람이다.

그렇기 때문에 마지막 파티에서도 거짓말을 해서는 안된다. 같은 원리로 6 7 8 이 참가하는 파티에서도 거짓말을 할 수 없고, 4 5 6 이 참가하는 파티에서도 거짓말을 할 수 없다.

그렇기 때문에 이 예제의 정답은 0 이다.

이 문제를 이렇게 풀었다.

1. knownList 의 사람들을 Union 한다.
2. 파티를 입력 받고, 각 파티의 사람들을 Union 한다.
3. knownList 의 아무 사람이나 뽑아서 Root 를 찾는다.
4. 파티를 다시 순회하면서 find 값이 Root 인지 체크한다.

핵심은 3, 4다. Union-Find 의 개념을 확실히 이해해야 생각할 수 있는 풀이 방법이였던거 같다. 집합 안의 아무 원소나 뽑아서 Find 연산을 하면 Root 를 구할 수 있다. 그리고 Union 연산에서 이미 Root 는 정리된다.

파이썬 코드

import sys
N, M = map(int, sys.stdin.readline().split())
knownList = list(map(int, sys.stdin.readline().split()))
parent = [x for x in range(N+1)]


def findParent(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = findParent(parent[x])
        return parent[x]


def union(a, b):
    pa = findParent(a)
    pb = findParent(b)
    if pa < pb:
        parent[pb] = pa
    else:
        parent[pa] = pb


parties = []
for _ in range(M):
    inputList = list(map(int, sys.stdin.readline().split()))
    parties.append(inputList)

# 진실을 아는 사람이 없다면, 모든 파티에서 거짓말.
if knownList[0] == 0:
    print(M)
    sys.exit(0)

# 먼저 진실을 아는 사람들을 하나의 집합에 묶는다.
tempRoot = knownList[1]
for x in knownList[1:]:
    union(tempRoot, x)

for party in parties:
    tempRoot = party[1]
    for person in party[1:]:
        union(tempRoot, person)


knownSetRoot = findParent(knownList[1])
answer = 0
# 다시 파티를 훑으면서, known 집합에 없는 사람들만 참여하는 파티에선 거짓말을 한다.
for party in parties:
    can_she_lie = True
    for person in party[1:]:
        if findParent(person) == knownSetRoot:
            can_she_lie = False
            break
    if can_she_lie:
        answer += 1

print(answer)