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) 을 통해 다음과 같이 리팩토링 할 수 있습니다.
시간 복잡도가 감소하므로 이 코드를 사용하는 것이 좋습니다.