[Union Find, Disjoint Set] 유니온 파인드 함수 구현 방법(재귀 사용!)

백준 1717번 문제를 풀 때 UnionFind를 사용하였다. 

1717번: 집합의 표현

 

Union Find는 그래프알고리즘의 일종으로 여러노드가 존재할 때 각 노드가 연결되어 있는지를 집합을 이용하여 확인하는 방식이다.

 

Union Find를 하기위해서는 크게 3가지의 함수가 필요하다. (꼭 필요한 함수는 2가지 이다)

 

1. make()함수

- 먼저 각 노드들의 부모노드를 저장할 parents배열을 초기화 시켜준다.

(parents 배열을 만드는 이유는 나중에 각 노드들의 부모노드를 비교하여 같은 집합에 속해있는지를 확인하기 위함이다.)

- make()함수의 초기상태로는 각 노드들이 연결되어 있지 않기 때문에 자기 자신을 부모노드로 초기화 시켜준다.

 

 

2. find()함수

- find()함수는 각 노드들의 부모노드를 찾아 반환해주는 함수이다. 이 함수를 이용하여 비교할 노드들의 부모노드를 찾아 만약 부모노드가 같다면 두 노드는 같은 집합안에 있다는 것을 뜻한다.

 

* 이 부분에서 굉장히 많이 헷갈렸다. Union Find의 개념만 살짝 알고 직접 구현해보지 않았던 나는 find()함수를

1번처럼 while문(반복문)을 이용하여 구현하였다. 

1. 반복문 이용                                                                                            2. 재귀함수 이용 

하지만 1717번 문제를 풀었을 때 정답은 인정 되었지만 수행시간이  3824ms가 나왔고, 이 코드는 문제가 있다 생각해서 다른 사람들의 코드를 분석해보았다. 

 

다른 사람들은 반복문을 이용하지 않고 2번 그림처럼 재귀함수를 이용하여서 풀었다. 재귀함수를 이용하였을 때에는 484ms가 나왔다. 거의 10배정도의 속도 차이가 났다.... 

 

내가 알기로는 재귀함수가 호출될때 마다 stack에 저장하고 하면서 속도가 반복문보다 느리다고 알고있었는데 이해가 가지 않았다. 이는 Union함수의 최적화를 알지 못했던 나의 실수였다. 최적화에 대해서는 마지막에 작성하도록 하고

 

3. Union()함수

마지막으로 Union()함수는 두 노드를 서로 연결시켜주는(집합의 관계가 되도록 하는) 함수이다.

먼저 각 노드의 부모노드를 find()함수를 이용해서 찾아온 후, 두 노드 중 부모노드가 작은쪽의 부모노드로 합쳐주는 함수이다. 이렇게 되면 각 노드에 속한 집합 노드들도 자연스럽게 부모노드가 연결되므로 하나의 집합이 만들어 진다.

 

* 그럼 마지막으로 Union함수의 최적화 방법에 대해 알아보기 전에 먼저 위 함수들에 대한 문제점을 살펴보겠다

1. 높이가 더 높은 트리가 높이가 낮은 트리 밑으로 들어가게 되면 트리가 점점 깊어질 위험이 있다. 즉 트리가 편향되어 만들어 져서 최악으로는 O(N)의 시간복잡도가 발생한다.

따라서 트리의 높이가 낮은 트리가 높은 트리 밑으로 들어가야 하는데 이를 위해서는 트리의 높이를 기록해두어야 한다.

 

2. find함수에서 나처럼 while문을 이용하여 부모노드를 탐색하면 매우 시간이 오래걸린다.

 

이 두가지를 해결하기 위한 방법이 Union함수의 트리 깊이를 저장하여 적절히 트리가 배치되도록 하는 Union by Rank 방식과 Find(x)를 실행하는 과정 가운데에서 경로 상의 모든 정점들을 곧바로 루트 정점 아래에 달아주는 Path Compression(경로압축) 방식이 있다.

 

1. Union by Rank : Rank 최적화는 트리가 균형잡혀있게 강제한다. 각 집합에 대해, ‘이 집합을 나타내는 트리의 높이’를 rank라는 변수에 저장한다. 그리고 두 집합을 합칠 때에는 rank가 작은 집합을, rank가 큰 집합 아래에 붙이는 형태로 구현한다.

또는, 각 집합에 대해 rank 변수를 유지하는 대신 size 변수를 유지해 같은 방법으로 최적화하는 Union by size 기법도 있다. 이 방법은 ‘smaller-to-larger trick’이라는 이름으로 일반적인 트리 알고리즘의 최적화에 쓰이곤 한다. 두 알고리즘 중 어떤 것이든 적용했을 때, 연산당 시간 복잡도는 O(logN)O(log⁡N) 으로 줄어든다.

보조정리 1. 정점 x가 속한 트리가 바뀌면, (rank 최적화를 수행할 경우) x의 rank는 언제나 1 이상 증가하고, (size 최적화를 수행할 경우) size는 언제나 두 배 이상 증가한다.

증명. 정점 x가 속한 트리가 바뀐다는 뜻은, x를 rank(size)가 더 크거나 같은 정점 y 아래에 붙인다는 것이다.

• rank[y]는 rank[x] 이상이므로, 합친 이후의 rank[x]는 rank[x] = rank[y]일 경우 rank[x]+1이거나 그렇지 않을 경우 rank[x]가 된다. 두 경우 모두, 합친 이후의 rank[x]는 rank[y]+1 이상이다.
• size[y]는 size[x] 이상이므로, 이므로 합친 이후의 size[x]인 size[x] + size[y]는 2 size[x] 이상이다.

더불어, 정점 x가 속한 트리가 바뀔 때마다 정점 x의 깊이는 1씩 증가한다는 사실을 알 수 있다.

보조정리 2. 모든 정점의 rank는 ⌈log2N⌉⌈log2⁡N⌉ 이하이고, 모든 정점의 size는 NN 이하이다.

증명. 모든 정점의 size가 NN 이하인 것은 정점의 개수가 NN개이므로 자명하다. 그리고,

• size가 1일 때, rank는 1.
• size가 3 이하일 때, rank는 2 이하.
• size가 7 이하일 때, rank는 3 이하.
• size가 15 이하일 때, rank는 4 이하.
• …

임이 귀납적으로 증명 가능하다. 따라서, 모든 정점의 rank는 ⌈log2N⌉⌈log2⁡N⌉ 이하이다.

위 두 보조정리로 인해, union by rank와 union by size의 시간 복잡도가 동시에 증명된다. Union by size를 사용한다고 하자. 어떤 정점 x에 대해, x가 속한 트리가 바뀔 때마다 size가 2배 이상 증가한다. 그런데, size가 NN 초과가 되는 것은 불가능하므로, x가 속한 트리가 바뀌는 횟수는 많아야 ⌈log2N⌉⌈log2⁡N⌉ 번이다. 그런데, 정점 x가 속한 트리가 바뀔 때마다 정점 x의 깊이는 1씩 증가한다. 초기에 모든 정점들은 자신이 속한 트리의 루트였으므로 깊이가 0이었다. 따라서 연산들을 수행한 이후에도 각 정점의 깊이는 ⌈log2N⌉⌈log2⁡N⌉ 이하이다. 따라서 find 함수는 언제나 ⌈log2N⌉⌈log2⁡N⌉ 개 이하의 정점을 순회하게 되고, O(logN)O(log⁡N) 시간에 작동한다.

Rank/Size compression만을 사용해도 트리의 균형이 보장된다! 이 성질은 KOI 지역예선 필기 시험에서도 물은 적이 있고, Heavy Light Decomposition 등 다양한 알고리즘의 시간 복잡도를 보장해주기도 하므로, 꼭 기억해두면 좋다.

- 출처 : https://www.secmem.org/blog/2021/04/19/Union-Find-Time-Complexity-Proof/#path-compression

Union Find의 시간 복잡도 증명

 

2. Path Compression

find 함수 내에서 2번처럼 재귀함수를 이용하면 Find(x)를 실행하는 과정 가운데에서 경로 상의 모든 정점들을 곧바로 루트 정점 아래에 달아주기 때문에 부모노드를 탐색하는 시간이 훨씬 줄어든다.

이 최적화 방법이 나의 수행시간을 3800에서 400으로 낮춰준 이유이다.

 

아래의 함수는 위 예시에 대한 코드이다. 두 함수를 비교해보면 재귀함수를 이용할 때에는 parents[a]를 변경시켜줘서 find함수를 수행할 때 마다 연결된 모든 노드에 대해 경로 최적화를 시켜주고

반복문을 이용할 때에는 변수 a를 변경시켜줘서 연결된 모든 노드가 아닌 부모노드의 바로 아래 노드만 최적화를 시켜준다. 

 

 parents = {0,1,1,2,3,4,5,7}일 때 둘을 비교해보면

 *    경로압축을 해주면 {0,1,1,1,1,1,1,7}
 *    경로압축을 안해주면 {0,1,1,2,3,4,5,7}이 된다.
 *    find함수를 수행할 때 경로압축을 해주면 나중에 union 할 때 부모노드를 찾을 때 속도가 훨씬 상승된다.

 

import java.util.Arrays;

public class test {
	static int parents[], N, M;

	private static int find(int a) {   // 경로압축 해줬을 때
		if(a!=parents[a])
			parents[a] = find(parents[a]);
		return parents[a];
	}
	
	private static int find(int a) {    // 경로압축 안해줬을 때
		while(a!=parents[a]) {
			a = parents[a];
		}
		return a;
	}
	
	static void union(int start, int end) {   
		int aRoot = find(start);
		int bRoot = find(end);
		if (aRoot != bRoot) {
			parents[bRoot] = aRoot;
			return;
		} else {
			return;
		}
	}

	public static void main(String[] args) {
		parents = new int[] {0,1,1,2,3,4,5,7};
		find(6);
		System.out.println(Arrays.toString(parents));
		
	}

}