[백준] 1043 - 거짓말 (분리집합 풀이)

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

1043번: 거짓말

분리집합 (유니온-파인드)를 사용하여 푸는 문제이다.

문제 분류를 보면 그래프 탐색으로도 분류가 되어있는데,

우선은 분리집합으로 풀어보았다.

 

이 문제는 시간제한도 2초로 넉넉한데, 파티당 인원수, 파티수, 총 사람 수가 매우 작다.

그래서 시간복잡도는 거의 신경쓰지 않고.. 그냥 최대한 되는 대로 풀어보았다.

 

---

풀이 아이디어

1. 분리집합 자료구조만 이해했다면 문제 해결 아이디어를 떠올리는 것은 어렵지 않다.

주어진 파티 정보를 순회 하면서, 한번이라도 마주치는 사람들을 모두 한 그룹에 묶는다.

 

1과 3이 만나면 (1, 3) 을 한 그룹에 넣고

2와 3이 만나면 (2, 3)을 한 그룹에 넣는데,

3이 이미 1과 같은 그룹이므로 묶어서 (1, 2, 3) 으로 묶는다.

 

비록 1과 2는 직접 만난 적은 없지만 (같은 파티를 참가한 적은 없지만)

3을 매개로 해서 이야기를 전해들을 수 있기 때문에 만난 것으로 간주한다.

 

이렇게 그룹을 묶는 작업이 사실상 분리집합 자료구조 이므로,

분리집합을 이용해, 만나는 그룹을 표현한다.

---

2. 하지만 또 다른 고민은, 해당 그룹 내 사람에게 진실을 말해야 하는지,

과장해서 거짓말을 해도 되는지 어떻게 판단할 것인가 이다.

우리가 갖고 있는 정보는, 진실을 아는 사람만 알고 있다.

진실을 아는 사람이 속해있는 그룹의 구성원인지 판단하는 것은 다른 문제이다.

 

나는 이 문제를, 분리집합 구현단계에서 조금 변형하여 해결하였다.

우선, find 를 수행할 때,

내가 진실을 아는데, 내 그룹이 진실을 모르는 그룹이거나

내가 진실을 모르는데, 내 그룹이 진실을 아는 그룹이면

진실을 모르는 쪽을 진실을 아는 쪽으로 고치도록 하였다.

 

그러면, 그룹의 대표자만 진실을 아는 것처럼 보이고,

진실을 모르고 있던 구성원은 여전히 모르는 것처럼 보인다.

 

 

그리고 merge는 기존 코드대로 작성하되,

merge를 한 직후, 흡수당한 쪽에 대해 다시 find를 진행하여

흡수한 쪽 대표자, 흡수된 쪽 대표자 둘 중 하나가 진실을 모른다면,

진실을 아는 것으로 고치도록 하였다.

 

물론 이 경우에도, 각 그룹의 대표자만 진실을 아는 것처럼 보인다.

---

3. 아직까지는 그룹 구성원은 진실을 모르는 것처럼 보이고, 그룹 대표자만 진실을 아는 듯 보인다.

이 상태로는 문제를 풀 수 없다.

 

예를 들어 대표자가 3인 진실을 모르는 그룹 (1, 2, 3) 에

진실을 아는 4가 merge 된다고 할 때,

2번 아이디어를 적용하면 (1, 2, 3, 4) 라는 그룹이 된다.

 

이 상태에서는 1, 2는 진실을 모르는 듯 보이기 때문에

3, 4 없이 1, 2만 있는 파티가 중간에 있다면

이 파티에서는 거짓말을 하게 된다.

 

따라서, 마지막에 각 파티를 체크할 때는 항상 find 연산과 함께 체크한다.

그러면 1, 2에 대해 find로 체크하는 순간 그룹의 대표자인 3과 진실을 아는지 여부가 다르기 때문에

1, 2 도 진실을 아는 것으로 수정된다.

 

또 하나, 간단한 팁은 각 파티를 체크할 때는, 파티의 구성원 1명만 체크하면 된다.

그 이유는 어차피 파티의 구성원은 모두 같은 그룹에 속해 있음이 보장되기 때문이다.

---

이 아이디어를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline

def find(p):
    if p == disjoint[p]:
        return p
    else:
        if say_truth[p] and not say_truth[disjoint[p]]:
            say_truth[disjoint[p]] = True
        elif not say_truth[p] and say_truth[disjoint[p]]:
            say_truth[p] = True

        disjoint[p] = find(disjoint[p])
        return disjoint[p]

def merge(a, b):
    a = find(a)
    b = find(b)
    disjoint[b] = a
    find(b)

# input
n, m = map(int, input().split())
know = list(map(int, input().split()))
cnt = 0

say_truth = [False for _ in range(n+1)]
disjoint = [i for i in range(n+1)]
parties = []

for i in range(1, len(know)):
    say_truth[know[i]] = True

# make group
for _ in range(m):
    party = list(map(int, input().split()))
    parties.append(party)
    p = party[1]
    for i in range(2, len(party)):
        merge(p, party[i])

# party check and count
for i in range(m):
    if not say_truth[find(parties[i][1])]:
        cnt += 1

# answer
print(cnt)