자료구조 | 유니온-파인드(Union-Find)

Union-Find 

Union-Find는 Kruskal 알고리즘을 구현하기 위해 핵심적으로 알아야 할 자료구조이다.

 

Disjoint Set(서로소 집합 자료구조)을 표현할 때 사용하는 자료구조이다. 

서로소 집합은 공통 요소가 하나도 없는, 즉 교집합이 전혀 없는 서로 다른 부분집합들을 의미한다.

그리고 Union-Find는 이 Disjoint-Set을 구성하고 각 요소에 대한 조작, 검색을 수행하도록 설계된 개념이다. 

 

구현

해당 자료구조는 언어 자체에 내장되어 있거나 그렇진 않고, 일반적으로 딕셔너리(트리 구조)로 구현한다. 

• Key = 노드
• Value = 해당 노드의 부모 노드 (* 루트 노드는 부모 노드로 자기 자신을 가리킨다.)

출처: https://hongjw1938.tistory.com/26

트리 구조의 부모-자식 관계를 이용하여 어떠한 부분집합의 개별 요소들을 연결한다.

그리고 트리 구조 꼭대기에 있는 루트 노드는 곧 그 집합을 대표하는 대표 노드의 역할을 한다. 

 

 

배열로도 구현할 수는 있지만 union 연산에 있어서 시간 복잡도가 O(N^2)이 될 수 있으므로, 비효율적이다.

• (참고: https://hongjw1938.tistory.com/26)

 

핵심 연산

이 자료구조는 1) 초기화 연산, 자신의 이름 그대로 2) Union과 3) Find 연산을 갖고있다.

1. make-set(i): 초기 집합을 세팅한다. 초기에 각 노드는 모두 루트 노드이므로, 부모 노드를 자기 자신으로 초기화한다.
2. union(i, j): i가 속한 트리와 j가 속한 트리를 찾고, 서로 다르다면 두 트리를 합친다.
3. find(i): i가 속한 트리의 루트 노드를 반환한다. 루트 노드는 해당 집합(트리)을 대표하는 노드이다. 따라서 루트 노드가 같은 원소는 서로 같은 트리에 속한다는 뜻이다. 

 

Union-Find 연산 최적화 기법

Union-Find 자료구조는 트리 자료구조를 활용하긴 하지만, 노드와 노드를 하나씩 연결하다보면 자칫하다간 연결 리스트의 형태를 띌 수 있게 된다는 한계점을 갖고 있다. 이는 연산의 효율성을 떨어트린다. 때문에 최적화를 통해 균형잡힌 트리의 모습을 유지해줄 필요가 있다.

 

그 방법론으로는 크게 두 가지가 제시된다. 

1. Union by rank: Union 연산을 수행할 때, 즉 두 트리를 합칠 때는 항상 rank가 낮은 트리를 더 높은 트리 밑으로 넣는다. 
   • rank를 저장하는 배열을 추가적으로 생성한다. 
   • (rank: 트리의 높이. 처음에는 0부터 시작한다.)
2. Path Compression(경로 압축): find(i) 수행시, i의 루트 노드를 찾는 과정에서 만나는 모든 노드의 부모 노드를 루트 노드로 통일시켜준다.

아래 그림을 예제로 사용해서 이해해보자.  

그림 출처: https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

 

1~7까지 노드가 있는 그래프에서 무작위로 union을 수행해봤더니 왼쪽 트리가 나왔다고 하자.

이때의 union-find 테이블은 다음과 같다. 

 

여기서 만약 find(0)을 수행한다면, 0번 노드의 루트 노드를 찾기 위해 0 -> 2 -> 3 -> 4 -> 5(루트) 순으로 찾아갈 것이다. 

따라서 자기 자신(0)을 포함한 2, 3, 4의 부모 노드도 5로 통일시켜준다.

 

그 결과, 테이블은 다음과 같이 재구성된다.

find(0) 과정에서 만나지 못한 1, 6, 7의 경우엔 아직 최적화되지 않고 그대로 2를 가리키고 있다.

 

find(0) 수행 예시: 0 -> 2 -> 3 -> 4 -> 5(루트) 순으로 간다. 따라서 자기 자신(0)을 포함한 2, 3, 4의 부모 노드도 5로 통일시켜준다. (만나지 못한 1, 6, 7의 경우엔 아직 최적화되지 않고 그대로 2를 가리키고 있음.)

 

 

이러한 최적화 기법들을 통해 Union-Find 알고리즘의 시간 복잡도는 거의 상수에 가까워진다.

 

 

코드로 이해하기

지금껏 다룬 핵심 연산(트리 초기화, union, find)과 최적화 기법(union by rank, 경로 압축)을 모두 포함해서 코드로 어떻게 구현하는지 알아보자. 

 

1. make-set(n)

• n = 초기화하려는 노드의 개수
• parent = 각 노드의 부모 정보
• rank = 각 노드의 랭크 정보 (union-by-rank를 위해)

### 초기화 연산 ###
def make_set(n): 
    # 각 노드의 부모 노드 정보를 저장하는 리스트 (리스트를 사용했지만 트리를 구현한 것임)
    parent = [i for i in range(n)]  # 초기에는 모든 노드가 루트 노드이므로 자기 자신을 부모로 가진다.
    
    # 각 노드의 랭크 정보를 저장하는 리스트 (Union by rank 적용을 위해)
    rank = [0 for _ in range(n)]
    
    return parent, rank

parent는 리스트로 선언되긴 했지만, 부모(값)-자식(index) 관계를 표현하므로 트리 구조를 구현한 것이다. 

 

 

2. union(parent, rank, i, j)

• i, j = 합치고자 하는 두 노드의 번호. i와 j가 속한 트리를 검사하고 합치게 된다.
• parent = 두 노드가 어느 트리에 속해있는지, 즉 루트 노드를 찾을 수 있도록 parent 배열 제공
• rank = union-by-rank 최적화를 위해 rank 배열 제공

### Union 연산 ###
def union(parent, rank, i, j):
    # i의 루트와 j의 루트를 찾음
    root_i = find(parent, i)
    root_j = find(parent, j)

    # 만일 두 노드가 이미 같은 집합이라면 union() 수행할 필요 X
    if root_i == root_j:
        return
    
    # Union by rank: 두 트리의 루트 노드의 랭크를 비교하여 작은 트리를 큰 트리 아래에 붙인다.
    if rank[root_i] < rank[root_j]: # 루트[j]의 랭크가 더 높다면
        parent[root_i] = root_j # 루트[i]의 부모를 자기 자신 -> 루트[j]로 할당
    elif rank[root_i] > rank[root_j]: # 루트[i]의 랭크가 더 높다면
        parent[root_j] = root_i # 루트[j]의 부모를 자기 자신 -> 루트[i]로 할당
    else: # 두 루트의 랭크가 같다면
        parent[root_j] = root_i # 둘 중 하나(일반적으로 더 낮은 수)의 밑으로 통합시키고
        rank[root_i] += 1  # 트리 높이를 1 증가. (높이가 같은 걸 밑으로 붙였으니, 트리의 꼬리(?)가 더 길어짐)

 

 

3. find(parent, i)

• i = 루트 노드를 찾고자 하는 노드의 번호
• parent = 해당 노드의 루트 노드를 찾을 수 있도록 parent 배열 제공

### Find 연산  ###
def find(parent, i):
    # 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[i] != i:
        parent[i] = find(parent, parent[i])  # 경로 압축 (만나는 노드의 부모 노드를 루트 노드로 바꿔주기)
    # 자기 자신을 가리키면 루트 노드 (parent[i] == i)
    return parent[i]


#### Find 연산 (경로 압축 X 버전) ###
# 실제로 쓸 일은 없으니 이해용으로만 보기! 
def find(parent, i):
    # 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[i] != i:
        find(parent, parent[i])  
    # 자기 자신을 가리키면 루트 노드 (parent[i] == i)
    return i

 

---

복습할 때는 안 보고 백지에 필기해보기

 

 

---

참고한 자료

https://hongjw1938.tistory.com/26

알고리즘 - Union-Find(Disjoint-Set 구현하기)

 

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

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

 

https://blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)