[알고리즘] 유니온 파인드(Union-FInd)

개요

유니온 파인드(Union-Find)는 서로소 집합(Disjoint Set) 자료구조를 표현하는 알고리즘이다.

Disjoint Set은 상호 배타적인(공통 원소가 없는) 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.

본문

유니온 파인드 구현

유니온 파인드는 크게 세가지 연산으로 구성된다.

• 초기화 : N 개의 원소를 각각의 집합으로 초기화
• Union  : 두 개의 원소가 속한 각각의 집합을 하나로 합침
• Find : 원소가 속한 집합을 반환

유니온 파인드는 배열 구현과 트리 구현으로 나뉘는데, 주로 트리 구현을 이용한다.(트리가 더 빠르다)

배열 구현

배열 기반 구현은 매우 간단하다.

• 초기화 : Arr[i] = i 와 같이 원소를 각자의 집합에 초기화시킨다.
• Union : 모든 배열을 순회하며 합쳐질 번호 집합을 합칠 집합 번호로 교체한다. (O(N))
• Find : 배열의 index로 집합의 번호를 확인한다.(O(1))

트리 구현

트리 구현에서는 트리의 루트 노드를 해당 집합의 번호로 본다.

따라서 Find 연산 시 루트 노드를 찾아야 하며, 이에 따라 모든 자식 노드들은 부모 노드의 포인터를 갖고 있어야 한다.(부모는 자식의 포인터를 갖고 있을 필요가 없다.)

• 초기화 : 모든 원소를 루트 노드로 초기화한다.(자기 자신의 포인터를 가리킨다.)
• Union : 각 트리의 루트 노드를 찾고, 다르면 하나의 루트 노드를 다른 쪽의 자식으로 넣는다.
• Find : 노드의 부모 노드를 찾아가며 루트 노드를 찾는다.(O(h))

Union-by-rank

유니온 파인드의 트리 구현에 있어 최악의 경우 위와 같이 연결리스트 형태의 트리가 구성이 될 수도 있다.

이 경우 Union과 Find 둘 다 O(N)이 되어 버리며 배열 구현보다도 느려지게 된다.

이 문제는 Union-by-rank 즉, 랭크가 더 낮은 트리를 높은 트리에 넣는 방법으로 해결할 수 있다.

또한 랭크 대신에 트리의 사이즈를 사용할 수도 있다.

최악의 경우를 O(N)에서 O(logN)으로 개선 가능하다.

Path Compression

Find(1)의 경우 Path Compression

두번 째 최적화 방법으로 Path Compression(경로 압축)이 있다.

Find를 호출하면 특정 원소에서부터 부모 노드를 따라 찾아 올라갈 것이다.

루트 노드를 찾았으면 시작 원소에서부터 지나온 노드들의 부모를 루트 노드로 지정하는 것이다.

시간 복잡도는 역 아커만 함수(inverse Ackermann function) O(α(N))가 나오는데, 이는 모든 n에 대해서 5보다 작다.

 

참조

[자료구조]Union-Find: Disjoint Set의 표현

Union By Rank and Path Compression in Union-Find Algorithm

유니온 파인드(Union Find, Disjoint Set)