9. [Algorithm] Union-Find 알고리즘 (서로소 집합 Disjoint-Set)

Union-Find

• Disjoint-Set을 구현할 때 사용하는 알고리즘
  • 집합을 구현하는데 비트 벡터, 배열, 연결리스트를 사용할 수 있으나, 가장 효율적인 트리 구조를 이용하여 구현함
• 크루스칼 알고리즘에서 그래프의 최소 신장 트리(MST: Minimum Spanning Tree)를 찾는데 활용된다. (정점 연결 및 사이클 형성 여부 확인)
• 초기에 {0}, {1}, {2}, ... {n}이 각각 n + 1 개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려는 경우. 집합의 표현 - 백준1717번
• 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 가입한 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하는 경우. 친구 네트워크-백준 4195번

 

---

Disjoint-Set

서로소 집합 자료구조 라고 부른다.

• 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
  • 즉, 공통 원소가 없는 상호 배타적 인 부분 집합들로 나눠진 원소들에 대한 자료구조이다.

• 상호 배타적 을 확실히 이해해야 한다. → A와 B는 C라는 집단 안에 소속되어 있지만 서로 공통적인 부분은 없다는 뜻.
  예를 들어 남성과 여성은 상호 배타적이다 라고 말할 수 있다. 남성과 여성은 둘 다 '인간' 이라는 카테고리에 포함되지만 서로 다르기 때문.
  ←→ ※ 두 사건이 독립적인 것은 서로 아무 관련이 없다는 것을 말한다.
  예를 들어, A라는 사람이 공부를 하는 것과 B라는 사람이 음식을 먹는 것은 독립적인 사건이다. 서로에게 아무런 영향이 없다.

 

---

Union-Find 기능과 구현

먼저 union() 함수와 find() 함수의 기능을 간단히 정리한 후 Python 코드를 살펴보자.

• union(parent, x, y)
  • 합하기, 연결하기
  • x가 속한 집합과 y가 속한 집합을 합친다. 즉, x와 y가 속한 두 집합을 합치는 연산

 

• find(parent, x)
  • 찾기(속한 그룹 찾기 = 부모 찾기)
  • x가 속한 집합의 대표값(루트 노드 값)을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾는 연산

 

기본적인 구현 방법

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
# ------------------------------------------------------------

# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1)  # 부모 테이블 초기화

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# union 연산을 각각 수행
for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)

# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end = '')
for i in range(1, v + 1):
    print(find_parent(parent, i), end = ' ')

print()

# 부모 테이블 내용 출력
print('부모 테이블: ', end ='')
for i in range(1, v + 1):
    print(parent[i], end= ' ')

'''
입력 예시
6 4
1 4
2 3
2 4
5 6

출력 예시
각 원소가 속한 집합: 1 1 1 1 5 5 
부모 테이블: 1 1 2 1 5 5 
'''

위 코드는 기본적인 union-find 구현 방법이다. 하지만, 트리의 모든 높이를 탐색해야하는 최악의 경우에는 비효율적인 성능을 보여준다.

• 트리 구조가 완전 비대칭인 경우
• 연결리스트 형태
• 트리의 높이가 최대가 된다.
• 원소의 개수가 N일 때, 트리의 높이는 N - 1이므로 union()과 find() 함수의 시간복잡도는 모두 O(N)이 된다.
• 배열로 구현하는 것보다 비효율적이다.

따라서 우리는 좀 더 효율적인 union-find 알고리즘을 구현해야 한다.

---

최적화된 union-find 알고리즘

 

find 최적화 : Path Compression (=경로 압축)

• find 연산 수행 시 방문한 노드들에 대해, 노드들의 부모를 Root로 갱신시켜주는 방법이다.
• 따라서 다음에 find 연산을 수행했을 때, 경로를 압축한 노드들에 대해서는 부모값이 이미 Root로 갱신된 상태이므로,
  Root를 찾는 비용을 아낄 수 있다.

 

간단하게 그림으로 이해해보자.

• 다음 예시는 find(5)를 수행한 결과이다.
• 노드 5번의 Root를 찾는 과정에서 방문한 모든 노드들의 부모를 Root로 갱신해준다.
• 따라서 만약 이후에 find(4)를 수행한다면, 이미 Parent가 Root로 갱신된 상태이므로 Root를 찾는 비용을 절약할 수 있다.

 

find 함수 경로 압축 최적화 코드 (Python)

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

 

---

Union 최적화 : Union By Rank

• 트리의 높이는 탐색의 효율성과도 직접적으로 관련이 있다. 따라서 트리의 높이를 항상 작게 유지하는 것이 중요하다.
• 예를 들어, 아래 그림 예시를 통해 트리를 어떻게 합치느냐에 따라 탐색의 효율성이 달라짐을 확인할 수 있다.

• 따라서, 이를 구현하기 위해 기존 union 방식에 'rank'를 추가한다.
• rank는 트리의 높이와 관련된 정보를 담고 있다.
  하지만 엄밀히 말해서는 실제 트리의 높이와는 다를 수도 있다. 왜냐하면 위으 Path Compression 에 의해 트리의 높이는 동적으로 변하기 때문이다. Path Compression에 의해 트리의 높이는 작아질 수 있지만, Rank의 값은 작아질 수 없고 증가만 가능하다.
• 따라서 이제는 더 작은 rank를 가진 트리가, 더 큰 rank를 가진 트리에 붙는 방식으로 Union을 구현할 것이다.

 

간단하게 그림으로 이해해보자.

• rank가 1로 더 작은 오른쪽 트리가 
  rank가 2로 더 큰 왼쪽 트리에 붙는다.
• 따라서 트리의 높이를 작게 유지할 수 있다.

 

Union 함수 Union By Rank 최적화 코드 (Python)

사용할 때 rank도 입력해줘야 한다는 단점.

 

# union-by-rank 최적화 적용 union 함수
def union(parent, x, y, rank):
    rootX = find_parent(parent, x)
    rootY = find_parent(parent, y)

    # 두 값의 root가 같으면(이미 같은 트리) 연결 X(합치지 않음)
    if rootX == rootY:
        return

    # union-by-rank 최적화
    # rank가 더 큰 트리에 작은 트리를 붙인다.
    # 즉, 높이가 더 높은 쪽을 root로 한다.
    if rank[rootX] > rank[rootY]:
        parent[rootY] = rootX
    elif rank[rootX] < rank[rootY]:
        parent[rootX] = rootY
    else: # 만약 rank가 같다면 임의로 rootX 트리에 rootY 트리를 붙인다.
        parent[rootY] = rootX
        rank[rootX] = rank[rootX] + 1   # rootX 트리의 높이를 + 1

---

※ 기본 Union-Find 코드에 경로압축 기법 적용한 걸 디폴트로 이해하고, union-by-rank 기법은 이해해 놓고 필요할 때 적용 할 것.