[#1043] 거짓말

RookieAND·2022년 11월 24일

백준 유니온파인드 집합 코테

BaekJoon

목록 보기

34/42

❓ Question

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

📖 Before Start

Python에서 제공하는 Set 자료구조를 활용하여 문제를 풀었다.
하지만 이 외에도 Union-Find 알고리즘으로도 풀이가 가능하다.

이번 문제는 Set 자료구조와 교집합, 합집합 연산을 통해 구현이 가능했다.
하지만 Union-Find 라는 알고리즘 또한 활용이 가능하다는 것을 알았다.

✒️ Design Algorithm

Set 자료구조와 교집합, 합집합 연산을 통해 구현이 가능했다.

파티에 참여한 인원 N 과 M 개의 파티가 개최되었다.
파티에서 진실을 아는 인원이 있다면, 나머지 구성원들 또한 진실을 알게 된다.

지민이는 모든 파티를 순회하며 거짓말을 최대한 많이 해야만 싶다.
즉 진실을 모르는 이들만 모인 그룹을 찾아야 거짓말을 전파해야 한다.

따라서 처음에는 집합 (Set) 을 활용해야 하는 문제라고 생각했다.

💻 Making Own Code

❌ Wrong Code

import sys

read = sys.stdin.readline
N, M = map(int, read().split())
know_true = set(read().split()[1:])

parties = [set(read().split()[1:]) for _ in range(M)]

for party in parties:
    if know_true.intersection(party):
        know_true = know_true.union(party)

result = 0
for party in parties:
    if not know_true.intersection(party):
        result += 1
print(result)

접근은 좋았으나, 이 코드는 입력 순서 에 따른 오류를 잡지 못했다.

처음에는 모든 파티의 구성원 정보를 전부 입력 받은 후, 이를 한 번 순회하였다.
순회 과정에서 진실을 알게 된 이들과 동행한 사람들도 진실을 알게 되었으므로
해당 동행한 이들을 모두 합집합 연산 (union) 을 통해 포함시켰다.

그리고 다음 줄에는 다시 모든 파티를 순회하면서 최종적으로 산출된 집합을 통해
진실을 아는 이들이 파티에 섞여 있는지를 체크했다. 하지만 오답 처리를 받았다.

그 이유는 새롭게 진실을 알게 된 이들을 고려하지 않고, 연산을 진행했기 때문이다.
아래의 예시가 바로 내가 세운 코드의 반례였다.

기대한 값은 0 이였으나, 어째서인지 3 이 나온다.

위 예시에서 진실을 아는 이는 1번 이며, 이후 1번 은 4번 과 만나 진실을 듣는다.
그리고 4번 은 2번 과 만났기 때문에 지민이는 거짓말을 할 수 없는 게 정상이다.

하지만 상단의 코드에서는, 진실을 아는 이들을 추려내는 과정에서 이를 고려하지 않는다.
즉, 앞서 입력된 4번 과 2번 이 참석한 파티에서는 거짓말을 해도 된다고 판단한 것이다.

정석대로라면 1번 은 4번 과 진실을 듣고, 4번 은 2번 과 진실을 들어야 정상인데,
단순히 입력받은 순서대로만 이를 처리하면 1번 과 4번 만 진실을 들었다고 처리한다.
그렇다면 지민이는 2번 과 3번 이 모인 자리에서 안일하게 거짓말을 하다 들킬 것이다.

✅ Correct Code

import sys

read = sys.stdin.readline
N, M = map(int, read().split())
know_true = set(read().split()[1:])

# 파티 그룹을 우선 집계하여 이를 체크.
parties = [set(read().split()[1:]) for _ in range(M)]

# 파티를 진행하면서, 진실을 알게 된 이들을 체크.
for _ in range(M):
    for party in parties:
        # 파티 인원 중, 진실을 아는 이들이 있다면 모든 참가자를 포함시킴.
        if know_true.intersection(party):
            know_true = know_true.union(party)

print(know_true)

# 파티 구성원 중, 진실을 알게 된 이들이 포함되지 않은 파티만 체크.
result = 0
for party in parties:
    if not know_true.intersection(party):
        result += 1
print(result)

결국 거짓말을 하면 안되는 인물을 추가 반복을 통해 파악해야 했다.

따라서 정확하게 이를 해결하려면 파티의 수 (M) 만큼 탐색 과정을 또 거쳐야 한다.
그래야만 새롭게 진실을 전달받은 이들에 대해서도 올바르게 탐색을 마칠 수 있다.

✅ Correct Code (with Union Find)

import sys

# x 노드가 속한 집합의 루트 노드를 탐색하는 함수.
def find(x):
    if x != parents[x]:
        parents[x] = find(parents[x])

    return parents[x]

def union(a, b):
    a, b = find(a), find(b)

    # 둘 다 진실을 아는 경우, 굳이 Union을 안해도 됨.
    if a in know_true and b in know_true:
        return

    # a 가 진실을 아는 집합에 소속되어 있다면, b가 소속된 집합을 포함시킴.
    if a in know_true:
        parents[b] = a

    # b 가 진실을 아는 집합에 소속되어 있다면, a가 소속된 집합을 포함시킴.
    elif b in know_true:
        parents[a] = b

    # 루트 노드가 같지 않을 경우, 두 집합을 서로 이어줌.
    # 여기서는 노드의 값이 큰 것이 작은 것에 연결되게끔 함.
    else:
        parents[max(a, b)] = min(a, b)

read = sys.stdin.readline
N, M = map(int, read().split())
know_true = list(map(int, read().split()))[1:]

# 유니온 파인드 연산을 위해, 각 노드 별 루트 노드를 보관하는 list.
parents = list(range(N + 1))
parties = []

for _ in range(M):
    peoples, *party = list(map(int, read().split()))
    # 해당 파티의 참가자들을 대상으로 Union - Find 진행.
    for i in range(peoples - 1):
        union(party[i], party[i + 1])
    parties.append(party)

result = 0
for party in parties:
    for visitor in party:
        # 만약 해당 파티의 참가원이 속한 그룹의 루트 노드가 진실을 아는 이라면, 해당 파티 제외.
        if find(visitor) in know_true:
            break
    else:
        result += 1

print(result)