유니온 파인드/분리집합 알고리즘(백준알고리즘 1043번)

♣ 유니온 파인드란?

유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 분리집합 알고리즘이라고도 한다. 아래 집합을 보면 왼쪽은 두 집합에서 공통된 원소가 없고, 오른쪽은 공통된 원소가 있다. 공통된 원소는 서로소 집합이라고 한다. 

 

유니온 파인드는 서로소 집합 자료구조를 만들 수 있다. 집합에서 노드들을 합치고(union), 부모를 찾아(find) 서로소 집합을 찾는 알고리즘이다. 기본적으로 유니온 파인드는 트리 자료구조에서 사용한다. 

 

아래 그림처럼 두 개의 트리 구조가 있다고 생각해보자. 

 

이 두 개 트리를 하나로 합치려고 한다. 기본적으로 각 집합의 root node를 찾아서 더 높은 인덱스를 가진 쪽이 작은 쪽을 흡수하는 성질을 가진다. 즉 아래 그림과 같은 결과가 나올 것이다. 

 

Union

 

표로 정리하면 아래와 같다. 

 

union 연산 전

________________________________________________________________________________

노드 번호            1            2              3              4                    5                  6                     7

________________________________________________________________________________

부모 노드            3            3              3              5                    6                  6                     5

________________________________________________________________________________

 

 

union 연산 후 

________________________________________________________________________________

노드 번호            1            2              3              4                    5                  6                     7

________________________________________________________________________________

부모 노드            3            3              6              5                    6                  6                     5

________________________________________________________________________________

 

파이썬 코드로 나타내면 아래와 같다. 

 

find 함수를 이용하여 x 노드의 부모 노드를 찾는다. 위 그림을 예시로 a가 3, b가 6 일 때, union 연산 전에 a의 부모 노드는 3, b의 부모 노드는 6이다. 하지만 union 연산에서 a < b 가 성립하므로 a의 부모 노드인 parent[a] 가 b, 즉 6이 된다. 

 

 

 

Find

어떤 과정으로 Union 연산에서 부모 노드를 찾았는지 생각해보자. Find 연산은 어떤 노드가 주어질 때 이 노드의 부모 노드를 찾아주는 연산이다. 

 

find는 해당 노드의 값이 부모의 노드의 값과 같을 때까지 재귀함수로 실행된다. 즉, 최상단의 부모 노드를 찾을 때까지 실행되는 것이다. 

 

for문을 이용하여 find 연산을 n번 시행하면 배열은 아래 표처럼 변한다. 

 

___________________________________________________________________________________

노드 번호            1            2              3              4                    5                  6                     7

___________________________________________________________________________________

부모 노드            6            6              6              6                    6                  6                     6

___________________________________________________________________________________

 

 

 

♣ 백준 알고리즘 1034번

 

 

 

import sys
input = sys.stdin.readline

def find(x):
	if parents[x] != x:
		parents[x] = find(parents[x])
		
	return parents[x]
	
def union(a, b):
	a = find(a)
	b = find(b)
	
	if a<b:
		parents[b] = a 
		
	else:
		parents[a] = b
	print(parents)
	
#n = 사람 수, m = 파티 수 
n, m = map(int, input().split())
parents = [i for i in range(n+1)]
print(parents)

#t = 진실을 아는 사람의 번호들. 입력값에서 첫 번째 값 무시하고 나머지 값을 리스트 t로 저장한다. 
_,*t = map(int,input().split()) 
print(t)

#진실을 아는 사람들의 부모 노드를 0으로 설정한다.  
for i in t:
    parents[i] = 0
    
print(parents)

party = []
for _ in range(m):
	p, *q = map(int, input().split())
	#각 파티에 참석하는 사람의 번호 알아내기 
	party.append(q)
	if p == 1:
		continue 
	
	#파티에 참석하는 사람이 여러명일 때 유니온 파인드 실행 
	for i in range(p-1):
		print(q[i], q[i+1])
		union(q[i], q[i+1])
	
	#print(parents)
#print(party)

ans = 0 
for item in party:
	for j in item:
		#진실을 아는 사람이 한 명이라도 있으면 거짓말을 못하니 break 
		if find(parents[j]) == 0:
			break 
	else:ans += 1 
	
print(ans)

 

♣ 참고 자료

유니온 파인드: https://chiefcoder.tistory.com/55

[Algorithm] 유니온 파인드(Union-Find)란?? python에서 구현하기

https://www.jongung.com/292

[Python] 분리 집합, Union-Find에 대해서 알아보자!

https://my-coding-notes.tistory.com/471

[🥇4 / 백준 1043 / 파이썬] 거짓말

분리집합

https://4legs-study.tistory.com/94

분리 집합 (Disjoint Set) : Union-Find