알고리즘 - Union & Find

개념

그룹을 지을 때 사용할 수 있는 알고리즘이다. 처음에 자기 자신을 부모로 설정하고 조건에 따라 부모를 설정한다. Find는 자신의 최상위 부모를 찾는 역할을 한다. Union은 두 변수의 부모가 다르다면 하나의 최상위 부모를 다른 하나의 최상위 부모의 자식으로 만들어 두개의 그룹이 합쳐지는 기능을 수행한다.

• Union by Rank : 트리가 균형이 맞도록 한다. 각 집합에 대해 이 집합을 나타내는 트리의 높이를 rank 변수에 저장한다. 그리고 두 집합을 합칠 때 rank가 작은 집합을 rank가 큰 집합 아래에 붙힌다.
• Path Compression : 경로 압축(path compression)은 find 과정 가운데 경로 상의 모든 점들을 곧바로 루트 정점에 연결하는 방법이다. 이렇게 하면 위 그림과 같은 구조로 시간 복잡도가 훨씬 줄어들게 된다.

조건

• Cycle 구조가 생기면 안된다. 따라서 Union은 서로의 부모가 다를때만 해야한다.

사용하기 좋은 경우

1. 서로 중복되지 않는 부분 집합들로 나눌 때
2. 그룹의 수를 구할 때

구현 방법

1. Find

parent = [x for x in range(10)] # 자기 자신이 부모로 초기화

def find_parent(x, parent):
	if parent[x] == x: # x가 최상위 부모
			return x
	#x의 부모중 최상위 부모 찾기
	parent[x] = find_parent(parent[x], parent)
	return parent[x]

1. Union

def union_parent(a, b, parent):
	pa = find_parent(a)
	pb = find_parent(b)
	if pa == pb :
		pass
	elif pa < pb : # 더 큰애가 부모가 되게 설정
		parent[pa] = pb
	else:
		parent[pb] = pa

시간 복잡도

• O(M)+O(Mlog⋆N)+O(Nlog⋆N)=O((M+N)log⋆N)
• (M : find 연산 수, N : 트리가 바뀌는 횟수)