Algorithm - Union Find(합집합 찾기)

Union Find :

대표적인 그래프 알고리즘으로 합집합 찾기 라는 의미를 갖고 있음. / 서로소 집합(공통 원소가 없는 두 집합, example- {1,2}, {3,4} == 서로소 관계, {1,2}, {2,3} == 서로소 관계 아님), 상호배타적 집합(Disjoint-Set) 알고리즘 이라고도 불림. / 여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘. / 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조. / Union Find 알고리즘은 다른 고급 그래프 알고리즘의 베이스가 됨. (ex. Kruskal Algorithm)

 

Disjoint Set = 서로 중복되지 않는 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조. / 즉, 공통 원소가 없는, 상호 배타적인 부분들로 나눠진 원소들에 대한 자료구조. 

Union Find = Disjoint Set을 표현할 때 사용하는 알고리즘. / 집합을 구현하는데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그 중 가장 효율적인 트리구조를 이용하여 구현.

 

Union Find 알고리즘을 트리 구조로 구현하는 이유

- 배열 :

ㆍ arr[i] : i번 원소가 속하는 집합의 번호(루트 노드의 번호)

ㆍ make-set(x) : arr[i] = i와 같이 각자 다른 집합 번호로 초기화

ㆍ union(x, y) : 배열의 모든 원소를 순회하면서 y의 집합 번호를 x의 집합 번호로 변경 => O(N)

ㆍ find(x) : 한번만에 x가 속한 집합 번호를 찾는다. => O(1)

 

- 트리

ㆍ 같은 집합 = 하나의 트리, 집합 번호 = 루트 노드

ㆍ make-set(x) : 각 노드는 모두 루트 노드이므로 N개의 루트 노드 생성 및 자기 자신으로 초기화

ㆍ union(x, y) : x, y의 루트 노드를 찾고 다르면 y를 x의 자손으로 넣어 두 트리를 합함. => O(N)보다 작음.

ㆍ find(x) : 노드의 집합 번호는 루트 노드이므로, 루트 노드를 확인하여 같은 집합인지 확인. => 트리의 높이와 시간 복잡도가 동일. (최악 = O(N-1))

 

세 가지 연산을 이용하여 Disjoint Set을 표현

- make-set(x) : 초기화 / x를 유일한 원소로 하는 새로운 집합 만듦.

- union(x, y) : 합하기 / x가 속한 집합과 y가 속한 집합을 합친다. 즉, x와 y가 속한 두 집합을 합치는 연산

- find(x) : 찾기 / x가 속한 집합의 대표값(루트 노드 값)을 반환. 즉, x가 어떤 집합에 속해 있는지 찾는 연산.

 

여러 개의 노드가 서로 자유 분방하게 존재한다고 가정할 때, 모든 노드가 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있음 -> 모든 값이 자기 자신을 가리키도록 만듦 

1 ~ 8 까지의 숫자가 있을 때

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	2	3	4	5	6	7	8

1과 2가 연결되고 4와 5가 연결됬다 치면

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	1	3	4	4	6	7	8

이러한 연결성을 프로그래밍 언어로 어떻게 표현할수 있는가 에 대한 내용 = Union Find

2번째 Index의 값에 '1'이 들어감. -> 이렇게 부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합침(Union).

 

2와 3도 연결된다면?

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	1	2	4	4	6	7	8

위와 같이 표현됨. 1과 3이 연결되었는지는 어떻게 파악하는가? 1과 3은 부모 노드가 각각 1, 2로 다르기 때문에 부모 노드만으로는 한번에 파악할 수 없음. => 재귀 함수 사용.

3의 부모 노드를 찾기 위해서는 먼저 3이 가리키고 있는 2를 찾음. 2의 부모가 1을 가리키고 있으므로 1이 3의 상위 노드라는 것을 파악 가능. -> 재귀적으로 수행될 때 가장 효과적이고 직관적으로 언어를 작성할 수 있다고 함. 

결과적으로 Union연산이 다 수행되고 나면

노드 번호	1	2	3	4	5	6	7	8
부모 노드 번호	1	1	1	4	4	6	7	8

위처럼 표가 구성됨.

노드 1, 2, 3의 부모 노드가 모두 1이기 때문에 이 세가지 노드는 모두 같은 그래프에 속한다고 할 수 있음. 

Find 알고리즘은 두개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는 알고리즘.

 

Union Find 과정 

1. Init (초기화)

for (int i = 0; i < parent.length; i++) parent[i] = i;

최초 노드는 자기자신을 루트노드로

 

2. Find(x)

static int find(int x) { // x가 속한 그래프의 루트 노드를 반환
	if (x == parent[x]) return x; // x의 루트노드가 x일 경우(x와 연결된 노드가 없을 경우)
    
    return find(parent[x]); // 재귀를 이용해 부모노드 -> 부모노드 -> ... 의 방식으로 루트 노드를 찾아 리턴함
}

x가 속한 집합(그래프)의 root노드 반환

 

3. Union(x, y)

static void union(int x, int y) { // x와 y가 속한 두 그래프를 하나로 합침
	x = find(x); // 두 노드의 루트노드 찾기
    y = find(y);
    
    if (x > y) parent[x] = y; // 두 루트노드 중 원소 값이 더 작은 루트노드를 그래프의 루트노드로 선택함.
	else parent[y] = x;    
}

 

Union Find 의 시간 복잡도 :

일반적으로 트리의 높이만큼 탐색하는 O(logN)임. 트리를 형성하는 과정에서 Skewed Tree가 될 수 있음, 이렇게 될 경우 O(N).

효율성을 위해 Find 과정에서 경로 압축을 할 수 있음. 경로 압축시, find 함수 호출할때마다 트리의 높이가 매번 바뀌므로 수행시간이 변하게 됨. 경로 압축을 한 find 의 시간 복잡도는 O(a(N))이 됨. a(N)은 아커만 함수를 의미. 아커만 함수에서 N이 2^65536일 때, 아커만 함수의 값은 5가 되므로 상수의 시간 복잡도를 갖는 것과 같다고 함.

코드 ->

static int find(int x) {
	if (x == parent[x]) return x;
    
    return parent[x] = find(parent[x]);
}

static void union(int x, int y) {
	x = find(x);
    y = find(y);
    
    if (x == y) return;
    if (rank[x] < rank[y]) parent[x] = y;
    else parent[y] = x;
    if (rank[x] == rank[y]) rank[x]++;
}