[BOJ] 1043번 - 거짓말 (Union - Find 정리)

최근에 서로소의 집합에 대해서 공부를 해봤다. 뭔가 새로운 것을 배운다는게 마냥 싫지 만은 않았고, 생각보다 신기했다.

첫번째 문제는 백준사이트의 1717번 문제이고 이 문제를 풀기 전에 풀어본다면 좋을 것 같다. 

기본적인 문제로 Union - Find 자료구조를 이해하는데 도움이 많이 됐다.

(백준의 알고리즘 분류에서 Union - Find는 서로소의 집합<disjoint Set>으로 표기 되어있었다.)

www.acmicpc.net/problem/1717

1717번: 집합의 표현

Union - Find 에 대해 간략하게 정리해보고자 한다.

 

먼저 각 원소들의 부모는 자기자신으로 초기화 한다.

 

<초기 상태>

i	0	1	2	3	4	5	6
parent	0	1	2	3	4	5	6

다음, Find 알고리즘을 보도록 하자. 부모를 보면서 따라가는 재귀함수로 표현이 된다.

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

parent[a] = find(parent[a]) 문장에서 의미하는 것은 해당 지나온 노드들의 parent를 최상위 루트로 만들어주는 것이다.

이렇게 되면 나중에 찾을 때 시간을 단축할 수 있다.

 

집합을 합치는 Union 알고리즘

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

    if parent_b < parent_a:
        parent[parent_a] = parent_b
    else:
        parent[parent_b] = parent_a

a의 최상위 루트노드의 부모는 자기자신을 가리킨다. 예를 들어 그림으로 설명하겠다.

 

a의 Root노드는 c가되고 c의 부모노드는 자기자신을 가지고 있다.

b의 Root노드는 e가되고 e의 부모 또한 자기자신을 가지고 있게 된다.

 

find() 함수로 a,b의 Root노드를 찾고, Root노드의 값이 작은 쪽이 합쳤을 때 Root노드가 되도록 한다.

Union 했을 때의 그림

c의 값이 작으니 c가 최상위 Root 노드가 되도록 한 그림이다.

이를 이용해서 1717번 문제와 밑에 나오게 될 1043번 문제를 풀 수 있다.

 

www.acmicpc.net/problem/1043

1043번: 거짓말

1. 입력을 받으면서 해당 각각의 파티에서 만나는 상대의 집합을 구해준다.

 

이 말의 뜻은 예를들어 1번과 2번이 지민이의 진실을 알고있다고 가정하자. < 중요 >

 

첫번째 파티: 3번   두번째 파티: 2번 3번   -> 이렇게 된다면 두 파티에서 전부 진실만을 얘기해야한다.

이유는 두번째 파티에서 2번이 진실을 알고 있기에 진실만을 얘기해야한다.

그렇다면 3번또한 진실을 알게 되는 집합에 속할것이 때문에 첫번째파티에서도 진실을 말해야 한다

 

2. 파티를 다시 순회하며 해당 파티에 과장을 해선 안되는 파티가 있는지 검사한다.

 

* 해당 하는 사람이 어디 속해 있는지 알려면 find() 를 통해 Root노드를 검사해 주면 된다.

 

from sys import stdin

std = stdin.readline

N, M = map(int, std().split())

parent = [0 for i in range(N+1)]

for i in range(N+1):
    parent[i] = i


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


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

    if parent_b < parent_a:
        parent[parent_a] = parent_b
    else:
        parent[parent_b] = parent_a


truth = list(map(int, std().split()))

#  진실을 말한 자
for i in range(1, 1 + truth[0]):
    parent[truth[i]] = 0

party_list = []

for i in range(M):
    party = list(map(int, std().split()))
    party = party[1:]
    flag = False
    for j in range(len(party)-1):
        union(party[j], party[j+1])

    party_list.append(party)

answer = 0
for party in party_list:
    flag = False
    for p in party:
        if find(p) == 0:
            flag = True
            break

    if not flag:
        answer += 1

print(answer)