Boj 1043 거짓말 Python - 분리 집합

 

* 정확하지 않은 내용을 담고 있을 수도 있습니다.*

 

 

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

 

분리집합이라는 새로운 자료구조를 배우기 좋은 문제이다.

 

우선 문제는 N명의 사람과 그 중 진실을 아는 사람, 그리고 M개의 파티가 입력으로 주어질 때, 지민이는 파티에 가서 거짓말을 해야 하는 상황이다. 하지만 진실을 알고 있는 사람을 비롯한 그들과 같은 파티에 참여했던 사람들이 있는 파티에서는 거짓말을 하지 못한다. 이때, 주어진 입력에 따라 지민이가 거짓말을 할 수 있는 파티의 수를 구하는 것이 문제이다.

 

주어진 조건을 다시 해석하면 문제의 사람들은 크게 진실을 아는 집합 KT (Know the Truth)와 진실을 알지 못하는 사람들의 집합으로 나뉜다. 이때, 지민이는 진실을 아는 사람의 집합 KT와 서로소인 집합의 파티에서만 거짓말을 할 수 있다.

 

즉, 주어진 입력을 토대로 진실을 알고 있는 사람의 집합을 만들고, 각각의 파티에 대해서 서로소 판정을 해준 후 개수를 세면 해결된다.

 

하지만 이 과정에서 한번더 생각해야 하는 것이 있다. 입력으로 주어지는 진실을 아는 사람들을 뿐만 아니라 파티에 참여함으로써 진실을 알게 된 사람들 또한 포함하여 합집합 연산을 해야 한다는 것이다. 

 

그렇다면 두 원소가 주어졌을 때 서로 같은 집합에 속하였는지 판정한 후, 서로 다른 집합에 속해있으면 두 집합을 합쳐주는 그러한 연산이 필요해진다.

 

우선 첫번째로 제출한 풀이는 분리집합의 개념을 적용하지 않았다. (N, M<=50)으로 매우 작기 때문에 삼중 for문으로도 해결이 가능했기 때문이다. 제출한 코드는 다음과 같다.

n, m = map(int, input().split())
a, *tmp = map(int, input().split())
kt = set(tmp)
d = dict()
cnt = 0

for i in range(m):
    a, *party = map(int, input().split())
    d[i] = party
    for j in party:
        if j in kt:
            kt.add(k for k in party)
for _ in range(50):
    for i in range(m):
        party = d[i]
        for j in party:
            if j in kt:
                for k in party:
                    kt.add(k)
for i in range(m):
    party = d[i]
    flag = False
    for j in party:
        if j in kt:
            flag = True
            break
    if flag:
        continue
    cnt+=1
    
print(cnt)

 

두번째 풀이는 분리집합(Union Find) 개념을 적용하였다.

 

유니온 파인드는 다음과 같은 3개의 함수의 기능들로 설명될 수 있다.

 

우선 유니온 파인드의 기본 구조는 집합의 대표 원소를 루트 노드로 하는 트리의 구조이다. 이로써 루트 노드가 서로 같은 두 노드는 같은 집합에 속하는 것이다. 다음 함수는 특정 원소의 집합을 대표하는 값인 루트 노드를 반환해준다.

 

*노드가 단 하나 뿐일 때에는 자기 자신이 부모노드이다.

def find(x):
    if x == parent[x]:
        return x
    return find(parent[x])

 

특정 두 원소를 포함하는 두개의 집합을 합치는 연산은 다음과 같이 둘 중 하나의 루트 노드를 다른 하나에 연결시켜주는 방식으로 실현된다.

 

def union(a, b):
    a = find(a)
    b = find(b)
    parent[a] = b

 

동일 집합 여부의 확인은 다음과 같은 함수로 구현 가능하다. 

두 원소 a, b가 같은 집합에 속하였는지의 여부를 참, 또는 거짓으로 반환한다.

def same(a, b):
    return find(a) == find(b)

 

이제 위의 원리를 사용하여 문제를 풀이해보겠다.

우선은 입력으로 주어진 진실을 알고 있는 사람들을 하나의 집합으로 묶어준다(Union 연산)

그 후, m개의 파티들 또한 각각의 집합으로 묶어준다.

**이때 자연스럽게 진실을 알고 있는 사람들을 포함한 파티 인원들은 공통된 루트 노드 하나에 연결되게 된다.**

즉, 수동으로 갱신해줄 필요 없이 효율적인 합집합 연산이 진행된다는 것이다.

 

이후에는 집합 KT와 서로소인 파티의 개수를 세어주고 이를 출력하면 된다. 제출한 코드는 다음과 같다.

def find(x):
    if x == parent[x]:
        return x
    return find(parent[x])
    
def union(a, b):
    a = find(a)
    b = find(b)
    parent[a] = b

def same(a, b):
    return find(a) == find(b)

n, m = map(int, input().split())
parent = [i for i in range(n+1)]
a, *kt = map(int, input().split())
if  a!=0:
    kt_rep = kt[0]
    ans = 0
    for i in kt:
        union(kt_rep, i)
    d = dict()
    for i in range(m):
        a, *party = map(int, input().split())
        d[i] = party
        rep_p = party[0]
        for j in party:
            union(j, rep_p)
    for i in range(m):
        party = d[i]
        rep_p = party[0]
        if same(rep_p, kt_rep):
            continue
        ans+=1
    print(ans)
else:
    print(m)