유니온 파인드 알고리즘은 집합에 관한 알고리즘이다.
좀 더 상세히 말하자면, 집합의 구성요소들을 효율적으로 찾고,
다른 집합을 효율적으로 합치도록 만들어주는알고리즘이라 할 수 있다.
A = [1,2,3,4,5,….1000]
B = [1001, 1002, 1003, 1004, …., 2000]
라는 두 집합이 있다고 해 보자.
여기서 아무 두 수를 뽑아서 그 두 수가 동일한 집합에 속해있는지를 판단(find)하는 문제가 있다면?
<키 , 값> 의 자료구조(HashMap, Dictionary 등)를 사용하면 쉽게 풀린다.
각 집합의 구성요소들을 O(N)으로 한 번 스캔하면서,
<element 값, 집합의 이름> 의 구조로 저장해놓으면
두 element가 같은 집합에 속해있는지 O(1)의 시간복잡도로 판단할 수 있다.
하지만 두 집합을 합친다면(Union)?
둘 중 하나의 집합 요소를 다시 한번 풀 스캔하여 value값을 합쳐진 집합의 이름에 맞게 모두 수정해주어야 한다.
만약 어떤 문제에서 합침(Union) - 동일 집합인지 판단(find)의 질문이 빈번하게 발생(Q번이라 하자)하며,
집합의 크기가 매우 크다면?
위 방법으로는 O(N x Q) 의 시간복잡도가 소요될 것이다.
가령, 아주 대표적인 아래 백준 문제를 보자.
element는 최대 100만개(초기에는 각 element가 단일집합을 구성함),
Union/find 연산은 최대 10만개가 주어진다.
위 방법으로 Union을 연산한다면 Union이 발생할 때 마다 O(집합의 크기) 의 시간복잡도가 발생할 것이고,
Union/Find 연산이 최대 10만개 이므로 어마어마한 복잡도가 발생한다.
이러한 문제를 트리구조를 통해 효율적으로 해결하도록 도와주는 유니온 파인드 알고리즘을 알아보자.
기본 원리는 다음과 같다.
유니온파인드는 Union함수와 find함수를 각각 구현하여 문제에서 필요한 부분에 활용한다.
참고로 union 이라는 word는 예약어로 쓰이는 경우가 있기에, union이 아닌 merge로 표현하기도 한다.
파이썬으로 find함수를 구현한 결과는 아래와 같다.
def find(parents, num):
if parents[num] == num: return num # root노드는 항상 자기 자신의 번호를 가리킨다.
res = find(parents, parents[num])
parents[num] = res # 경로압축최적화
return res
parents = [i for i in range(n + 1)] # n개의 노드가 있을 때
먼저 parents 배열에 자기 자신을 root로 하는 모든 노드를 설정한다.
그리고 재귀함수로 root노드를 찾아가는 find함수를 구현하는데,
여기서 재귀함수의 return값을 최종 root노드 값으로 하여
재귀함수가 반환될 때 각 노드의 parents 배열값을 갱신한다.
이를 경로압축최적화라고 하며, 이 경우 효율성이 더욱 증가한다.
만약 트리가 다음과 같이 일렬로 쭉 늘어진 형태라고 생각해보자.
1 - 2 - 3 - 4 - 5 (root)
이 경우 find를 할 때 O(N)의 시간복잡도가 든다. 일렬 구조가 변하지 않기 때문이다.
그러나, 어차피 1,2,3,4 의 root는 5로 동일하다면, find를 하면서 아래와 같은 구조로 만들어버리면?
5(root)
/ | | \
1 2 3 4
find함수 수행과 동시에 1,2,3,4가 바로 root 노드에 붙어버리기 때문에,
다음번 find부터는 연산 시간을 크게 줄일 수 있다.
파이썬으로 Union함수를 구현한 결과는 아래와 같다.
def union(parents, first, second):
# first, second 노드의 root를 각각 구한다.
rootA = find(parents, first)
rootB = find(parents, second)
# root 노드가 같으면 같은 집합에 속해있다는 의미이므로 바로 return한다.
if rootA == rootB: return
# root 노드가 다르면 root노드를 어느 한 쪽에 맞춰준다.
parents[rootB] = rootA
return
결국 find 함수만 잘 구현한다면, union 함수는 구현이 상당히 간단하다.
그 말은 즉 Union 함수의 효율은 결국 find 함수에 종속된다는 의미이기도 하다.
Union 과정에서 사용되는 find 함수가 경로압축 최적화가 되어있지 않다면?
결국 root 노드를 어느 한 쪽 맞추어야 하기 때문에,
자칫하다가는 일렬로 쭉 늘어진 트리구조처럼 형성될 가능성이 있다.
이를 방지하기 위해 Union 함수도 Find 함수의 경로압축최적화와 마찬가지로 최적화를 할 수 있다.
바로 두 노드를 합칠 때 짧은 트리를 긴 트리에 붙임으로서 트리의 높이가 길어지는 것을 방지하는 것이다.
이를 Union-by-rank라고 하며,
rank 배열에 해당 노드의 깊이를 기록하여 rank배열값의 비교를 통해 어디에 붙일지 정하는 것이다.
그러나 위 find 함수에서 살펴본 경로압축최적화를 활용하면
루트 노드 바로 아래에 다른 가지들이 붙게 되므로, 깊이를 별로 신경쓸 필요가 없게 된다.
이 유니온 파인드 알고리즘의 find() 함수의 시간복잡도는 O(a(n)) 이라고 하며,
a는 애커만 함수로 우리가 상상할 수 있는 모든 크기의 n에 대해 4 이하의 값을 가지는 값이다.
즉 모든 입력에 대해 실질적으로 상수시간에 동작한다고 한다.
구현이 간단하고 성능이 좋으므로 한번 익히고 나면 활용에는 큰 무리가 없으나,
유니온 파인드의 개념과 활용법 자체를 모른다면 위 백준 문제처럼 n이 매우 큰 문제는 TLE가 나기 마련이다.