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

유니온 파인드란?

• 대표적 그래프 알고리즘으로 서로소 집합 ( Disjoint - set ) 를 찾는 알고리즘
  • Disjoint - set : 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하는 자료구조
• 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 서로 같은 그래프에 속하는지 판별하는 알고리즘

• 3가지의 연산으로 이루어져 있다.
  • make : 가장 작은 단위의 단위 집합을 만드는 연산 (초기화 연산)
  • Find : 해당 노드가 속한 집합을 찾는 연산 ( 해당 노드가 속한 집합의 대표자를 찾는 연산 )
  • Union : x가 속한 집합과 y가 속한 집합을 합치는 연산

 

보통 연결리스트 혹은 트리로 구현하는데 연결리스트로 구현하기보다 자신의 집합에 속해있는 부모의 관계를 이용해 배열로 구현한다.

---

과정

1. Make-set

본인이 대표자인 서로소 집합을 만든다.

2. Union

 인자로 주어진 두 노드를 합친다. 합치는 노드의 대표자를 변경시킨다.

3. Find

 find 연산을 통해서 d가 속한 집합의 대표값이 c라는 것을 알 수 있다.

---

Path Compression

유니온 파인드는 문제점이 있는데 바로 find 연산 수행 시 path가 길어질 수 있다는 점이다.

최악의 경우는 경로로 인해 O(N)까지 가능하고 이런 경우는 부모를 찾는 단계가 늘어나며 시간, 메모리 초과가 날 수 있다.

 

Path Compression을 적용하면 해결 가능하다.

 

Find-set을 행하는 과정에서 만나는 모든 노드들이 직접 root 노드 (대표자) 를 가리키도록 포인터를 바꾸어 주면 Find-set을 수행한 노드들은 모두 대표자를 가리키기 때문에 더 효율적으로 find를 수행할 수 있다.

 

단, Find-set을 호출해야 수행되기 때문에 Find-set을 하지 않으면 바뀌지 않는다.

---

구현

1. makeSet 함수

parents는 i 노드의 부모 노드를 나타내고 N개의 노드가 존재하는 집합으로 각자 본인을 부모 노드로 초기화시킨다.

public static void makeSet() {
        for (int i = 0; i < N; i++) {
            parents[i] = i;
        }
    }

2. find 함수

대표가 본인인 노드를 찾을 때 까지 재귀함수로 트리를 탐색한다.

중간 단계에서는 Path Compression을 적용해 부모를 바로 루트 노드로 변경시킨다.

public static int find(int a) {

	if(parents[a] == a) return a;

	return parents[a] = find(parents[a]);

}

3. union 함수

public static boolean union(int a,int b) {

       int aRoot = find(a);
       int bRoot = find(b);

       if(aRoot == bRoot) return false;

       parents[bRoot] = aRoot;
       return true;
 
 }