[알고리즘] Union - Find 알고리즘

Disjoint Set 분리 집합

분리 집합은 서로소 집합이라고도 합니다. 용어의 의미처럼 분리 집합은 다음과 같은 특징을 가진다.

전체집합 U에 대해, U의 분리 집합 A, B는 다음 조건을 만족한다.

 - A, B는 U의 부분집합이다.

 - A, B는 공통 원소를 가지지 않는다.

 - A, B의 합집합이 곧 전체집합 U이다. (A, B에 속하지 않는 U의 원소가 없어야 한다.)

 

Union-Find 알고리즘

union-Find 알고리즘은 그래프 알고리즘 중 하나로 서로소 집합, 상호배타적 알고리즘이라고도 불립니다.

 

여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다.

 

노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어집니다.

 

 

 

동작과정

• 노드는 4개로 구성되어 있고
• parent[node]는 부모 노드번호로 가정할 때 다음과 같은 동작과정으로 이루어져 있습니다.

 

 

파이썬 예제 코드

find 함수 부분을 '경로 압축' (Path Compression) 을 통해 다음과 같이 리팩토링 할 수 있습니다.

시간 복잡도가 감소하므로 이 코드를 사용하는 것이 좋습니다.