Union-Find

개념

---

서로 중복되지 않는 부분 집합들을 표현할 때 사용하는 알고리즘

해당 알고리즘에 필요한 연산은 부분 집합들을 서로 묶는 연산(Union), 해당 원소가 어느 집합에 속해있는지 찾는 연산(Find)이 있습니다.

 

 

부분 집합들을 표현하는 방법

---

배열

해당 원소가 몇 번째 집합에 속해 있는지 각각의 원소마다 표시합니다.

1번째 부분 집합 : {0, 1, 2}

0 -> 1, 1 -> 1, 2 -> 1

Union 연산: 모든 원소에 대해서 몇 번째 집합에 속해 있는지에 대한 수정이 일어납니다.( O(N) )

Find 연산: 해당 원소가 몇 번째 집합에 속해있는지 바로 찾을 수 있습니다.( O(1) )

 

트리

부분집합마다 트리를 생성하여 각 원소가 부모 원소를 표시하고 있습니다(루트 원소는 자기 자신을 표시)

1번째 부분 집합 : {0, 1, 2}

0 -> 1, 1 -> 2, 2 -> 2

Union 연산: 각 집합의 루트 원소들을 연결합니다.(루트 원소를 확인하는 Find 연산이 대부분의 시간 차지)

Find 연산: 루트 원소를 확인하여 어느 집합에 속해 있는지 찾을 수 있습니다.(최악의 경우 O(N-1))

 

 

연산 과정(트리)

---

Union

0	1	2	3	4
1	2	2	4	4

위 배열은 {0 -> 1 -> 2}, {3 -> 4} 부분집합을 나타낸 배열입니다.

두 배열을 합치는 과정을 진행하겠습니다.

 

0	1	2	3	4
1	2	2	4	2

두 번째 부분집합의 루트 원소가 첫 번째 부분집합의 루트 원소를 가리켜서 합쳐진 부분집합을 나타내었습니다.

{0 -> 1 -> 2, 3 -> 4 -> 2}

 

 

Find

0	1	2	3	4
1	2	2	4	2

위 배열에서 0번 원소와 3번 원소가 같은 부분집합인지 알아보겠습니다.

0번의 루트 원소 찾는 연산을 하면 부모 원소를 따라가서 2번이 루트 원소인 것을 알 수 있습니다.

3번의 루트원소 찾는 연산을 하면 부모 원소를 따라가서 2번이 루트 원소인 것을 알 수 있습니다.

결국 둘은 같은 부분집합에 속해 있습니다.

 

 

트리의 문제점

---

Find 연산을 할 때에 제일 단말 원소부터 탐색을 시작하면 시간이 오래 걸린다는 단점이 있습니다.

이것을 위해서 트리를 최적화할 필요가 있습니다.

 

두 가지 방법으로 최적화를 거쳐 보겠습니다.

 

Union 연산 최적화

Union 연산을 할 때, 두 개의 부분집합을 비교해서 원소의 수가 더 적은 부분 집합의 루트 원소가 원소가 더 큰 부분 집합의 루트 원소를 가리키게 됩니다.

이유는 합치는 과정에서 한 부분집합은 트리의 높이가 증가할 수밖에 없는데 이를 최소화하기 위해서입니다.

 

다음은 연산 코드입니다.

private static void unionGroup(int a, int b) {
   // a, b의 루트원소를 구합니다
   int aRoot = findRoot(a);
   int bRoot = findRoot(b);

   // 부분집합 a의 원소의 개수가 더 클 경우 부분집합 a에 부분집합 b를 속하게 합니다
   if(size[aRoot] >= size[bRoot]) {
  	arr[bRoot] = aRoot;
   }
   else {
  	arr[aRoot] = bRoot;
   }
}

 

 

Find 연산 최적화

Find 연산을 하면서 부모 원소를 탐색할 때 루트 원소를 가져와서 표시를 할 수 있습니다.

 

0	1	2	3	4
1	2	3	3	3

해당 부분집합은 다음과 같습니다. {0 -> 1 -> 2 -> 3, 4 -> 3}

해당 배열을 0번 원소에 대해 최적화 Find 연산을 진행해 보겠습니다.

 

0	1	2	3	4
3	3	3	3	3

다음과 같이 변경되었습니다. {0 -> 3, 1 -> 3, 2 -> 3, 4 -> 3} 

0이 부모 원소를 탐색하면서 탐색한 모든 원소에 루트 노드를 표시한 것을 볼 수 있습니다.

 

다음은 연산 코드입니다.

private static int findRoot(int a) {
  // 루트 원소일 경우 return
  if(arr[a] == a) return a;
  // 탐색하는 원소에 루트 원소를 표시하면서 return
  return arr[a] = findRoot(arr[a]);
}

 

 

References

---

https://ohgym.tistory.com/9

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html