분리 집합은 두 집합의 관계르 나타내는 것으로 두 집합 A와 B의 교집합이 공집합일 때 A와 B는 분리 집합이라고 한다. 집합의 요소를 놓고 요소들이 포함된 집합이 같은 집합인지 분리 집합인지 확인하고, 두 분리 집합을 하나로 병합하는 알고리즘을 유니온 파인드라고 한다.
1. 분리 집합(Disjoint set)
두 집합 A = {1, 2, 3, 4, 5}와 B = {5, 6, 7, 8, 9}는 '5'를 공통 원소로 갖는다. 이 경우 A, B는 분리 집합이 아니다. 집합 C = {10, 11, 12, 13, 14}가 있을 때, A∪B와 C는 공통 원소가 없는 분리 집합이다. A와 C도 분리 집합이고 B와 C도 분리 집합이다.
여러 정점을 놓고 간선으로 연결한 상태가 주어졌을 때, 정점과 간선을 거쳐 연결된 정점들을 하나의 집합으로 생각하면 연결되지 않은 정점들의 집합은 서로 분리 집합이라고 볼 수 있다. 분리 집합을 모두 파악하기 위해서는 깊이우선탐색, 너비우선탐색 등을 이용한 탐색을 통해 확인할 수 있다. 이 경우 모든 정점을 최소 한 번씩은 탐색해보아야 한다. 하지만 분리 집합 전체를 파악하지 않고 주어진 두 요소 a, b가 서로 분리된 집합에 포함되어있는지 여부만을 판단한다면 정점을 모두순회할 필요 없이 a, b가 '어떤 집합에 포함 되었는지'만 파악하면 된다. 그리고 그 방법은 유니온 파인드 알고리즘이 대표적이다.
2. 유니온 파인드(Union-Find)
유니온 파인드는 집합을 하나의 트리 구조로 관리하며 요소들이 정점이 된다. 두 요소 a, b를 각각 트리 탐색하여 루트를 발견했다. a의 루트는 a'이고 b의 루트는 b'이다. 하나의 트리에 있는 모든 정점은 같은 루트를 갖기 때문에 a와 b는 서로 다른 집합에 있음을 알 수 있다. 여기서 요소 c가 새로 추가되었다. c는 a와 같은 집합에 있다. 그렇다면 여기서 c를 a'이 루트인 트리의 리프로 추가할 수 있다. 여기서 c가 b가 있는 집합에도 포함되었다고 해보면 c는 b'으로도 이어지게 된다. 두 트리 중 무엇이 루트가 되건 상관 없지만 편의상 a'가 b'트리의 루트가 된다면 이제 a'가 루트인 트리와 b'이 루트였던 트리의 노드 모두가 a'를 루트로 갖는다. 이렇게 두 집합이 병합되었다.
유니온 파인드에서는 순회가 없는 자료구조이며 서로 다른 정점 간의 경로가 유일한 특성을 갖는 트리로 집합을 관리해 루트 노드의 요소를 대표값으로 요소가 '어느 집합에 포함 되었는지'를 파악한다. 집합에 요소를 추가하는 방법에 따라 트리의 깊이가 달라지며 탐색에 걸리는 시간은 트리의 깊이에 따라 달라진다. 따라서 유니온 파인드의 효율성은 여기에 달려있다고 볼 수 있다.
3. 잡기술
최소 신장 트리를 찾는 방법 중 하나인 크루스칼 알고리즘에서는 회로를 제거하는 과정에서 유니온 파인드가 아주 유용하게 쓰인다. 여기서 우수한 코드와 내 코드의 실행 시간 차이는 20배 정도였다. 대체 뭐가 이런 차이를 만들었는가. 연구해본 결과 시간을 단축시키는 요인은 다음과 같았다.
먼저 가장 큰 원인. 집합을 병합할 때 루트 노드를 어느 쪽으로 맞춰줄 것인가. 더 작은 쪽으로 맞춰주면 트리가 내림차순으로 정리된다. 이걸로 10배 이상 빠른 실행 속도를 만들 수 있었다.
다음으로 파이썬의 경우, 병합하는 함수를 따로 만들지 않는 편이 더 빨랐고, 루트를 찾는 함수의 경우는 루트를 변경하지 않기 때문에 함수 밖에서 루트를 관리하는 배열에 직접 접근하지 않도록 매개변수로 루트 배열을 넘겨주는 편이 좋다.
4. 소스코드
한 줄에 한 집합에 포함되어있는 두 요소 a, b가 공백으로 나뉘어 입력될 때, 유니온 파인드로 분리 집합을 관리하는 코드는 다음과 같다.
parent = [i for i in range(N+1)]
# 요소 k가 포함된 트리의 루트 찾기
def find(k):
while parent[k] != k:
k = parent[k]
return k
# 요소 a와 b를 연결해 하나의 집합으로 만들기
def union(a, b):
parent_a = find(a)
parent_b = find(b)
if parent_a < parent_b:
parent[parent_b] = parent_a
else:
parent[parent_a] = parent_b