[알고리즘] 백준 1043 거짓말

백준 1043 거짓말

문제의 키포인트는 진실을 아는 사람들의 리스트를 계속 갱신을 해줘야 하는데 그것을 어떻게 하느냐이다. 이러한 알고리즘에 최적인 유니온 파인드를 쓸 수 있다.

유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로서 상호 배타적 집합이라고 한다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘이다.

      

        
        
        
        
      
import sys
from collections import deque
import heapq
def find(a):
    if a == parents[a]: return a
    return find(parents[a])

def union(x,y):
    x = find(x); y = find(y)
    if x < y:
        parents[y] = x
    else:
        parents[x] = y
n,m = map(int,sys.stdin.readline().split())
k,*lists = map(int,sys.stdin.readline().split())   # 진실을 아는 사람들
parents = [i for i in range(n+1)] # 유니온 파인드 배열
for i in range(len(lists)): # 진실을 아는 자들의 부모 노드를 0으로 초기화
    parents[lists[i]] = 0

partys = []
for i in range(m):  # 파티를 훑음
    party = list(map(int,sys.stdin.readline().split()))[1:]
    if len(party) > 1:
        for t in range(len(party)-1):
            union(party[t],party[t+1])
         
    partys.append(party)

cnt = 0
for p in partys:
    for i in range(len(p)):
        if find(parents[p[i]]) == 0:
            break
    else:
        cnt += 1

print(cnt)

 

📌 유니온 파인드의 핵심은 서로 다른 A,B가 만났을 때 find(A)가 find(B)보다 작을 때 parents[B]에다가 find(A)를 갱신해줘야 한다는 것이다. 이런 과정을 계속 진행할 수록 집합이 계속하여 갱신될 것이다.