[파이썬으로 배우는 알고리즘] Union-Find 알고리즘

Union-Find의 개념

Union-Find 알고리즘을 알기 위해서는 Disjoint Set의 개념부터 알고 가야 합니다.

 

Disjoint Set이란?

Disjoint Set이란 상호배타적인 집합으로 서로 중복되지 않는 부분 집합들로 나눠진 원소들의 데이터를 처리하기 위한 자료구조입니다. 그렇다면 이런 자료구조는 왜 필요할까요? 

만약 어떤 그래프에서 한 노드와 또 다른 노드의 연결 여부를 파악한다고 해보겠습니다. 이럴 경우 완전 탐색 알고리즘인 DFS와 BFS 알고리즘으로 파악할 수 있겠죠? 하지만 할 때마다 이런 탐색을 한다고 하면 한 번의 탐색당 O(N)라는 시간 복잡도를 갖게 되고, 이는 매우 비효율적인 탐색이 될 수 있습니다.

이를 해결하기 위해서 Disjoint Set을 사용해 연결된 노드끼리 그룹으로 묶어서 연결 여부를 보다 효율적으로 파악할 수 있습니다.

 

Union-Find란?

Union-Find 알고리즘은 바로 이 Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 자료구조를 사용하여 구현할 수 있습니다.

 

2022.07.08 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 트리(Tree)

[파이썬으로 배우는 자료구조] 트리(Tree)

 

Union-Find의 연산

1) makeset(x)

x만을 원소로 가지는 새로운 집합을 만듭니다.

2) union(x, y)

x가 속한 집합과 y가 속한 집합을 하나로 합칩니다.

3) find(x)

x가 어떤 그룹에 속하는지 파악합니다. (루트 노드 반환)

---

Union-Find의 동작

Union-Find 과정

union(1, 2), union(2, 3), union(4, 5), union(4, 6), union(6, 7) 순서대로 연산

 

1) 위와 같이 1부터 8까지 적힌 노드가 있습니다. 또한 루트 노드를 가리키는 리스트를 만들어 처음에는 각 노드가 자신을 가리키도록 리스트를 초기화 시켜줍니다.

 

2) union(1, 2) 연산 - 1과 2의 루트 노드를 찾습니다. 합칠 때는 루트 노드가 더 작은 쪽으로 합치며 노드 1이 루트 노드가 더 작기 때문에 리스트에서 2의 루트 노드를 노드 1의 루트 노드인 1로 바꿔줍니다.

 

3) union(2, 3) 연산 - 2와 3의 루트 노드를 찾습니다. 노드 2의 루트 노드가 더 작기 때문에 리스트에서 3의 루트 노드를 노드 2의 루트 노드인 1로 바꿔줍니다.

 

4) union(4, 5) 연산 - 4와 5의 루트 노드를 찾습니다. 노드 4의 루트 노드가 더 작기 때문에 리스트에서 5의 루트 노드를 노드 4의 루트 노드인 4로 바꿔줍니다.

 

5) union(4, 6) 연산 - 4와 6의 루트 노드를 찾습니다. 노드 4의 루트 노드가 더 작기 때문에 리스트에서 6의 루트 노드를 노드 4의 루트 노드인 4로 바꿔줍니다.

 

6) union(6, 7) 연산 - 6과 7의 루트 노드를 찾습니다. 노드 6의 루트 노드가 더 작기 때문에 리스트에서 7의 루트 노드를 노드 6의 루트 노드인 4로 바꿔줍니다.

 

이렇게 리스트를 갱신할 수 있고, 이제 이 리스트를 각각의 루트 노드 번호를 따라 그룹 지을 수 있습니다!

 

{1, 2, 3}, {4, 5, 6, 7}, {8} -> 세 개의 트리

---

Union-Find의 구현

코드

def find(x):
    # 루트 노드를 찾을 때 까지 재귀 호출
    if root[x] != x:
        return find(root[x])
    return x
    
def union(x, y):
    x = find(x)
    y = find(y)
    
    # 더 작은 루트노드에 합친다.
    if x < y:
        root[y] = x
    else:
        root[x] = y


if __name__ == "__main__":
    SIZE = 8
    root = list(range(SIZE+1))
    union(1, 2)
    print(root)
    union(2, 3)
    print(root)
    union(4, 5)
    print(root)
    union(4, 6)
    print(root)
    union(6, 7)
    print(root)

실행 결과

하지만 이 코드는 트리 구조가 완전 비대칭인 경우 높이가 최대가 되며 그럴 경우 트리의 높이는 N-1로 union, find의 시간 복잡도가 O(N)이 됩니다. 

ex) 1, 2, 3, 4, 5의 노드에 대해 union(4, 5), union(3, 4), union(2, 3), union(1, 2) 연산을 한 경우

 

이 경우 find(5) 연산을 할 때마다 루트 노드까지의 탐색 필요!

 

따라서 더 효율적인 연산을 위해 find함수를 다음과 같이 바꿔줍니다.

 

개선 코드

def find(x):
    # 루트 노드를 찾을 때 까지 재귀 호출
    if root[x] != x:
        # 경로 압축
        root[x] = find(root[x])
    return root[x]

이 코드로 바꾸고 위에 있는 union 연산을 한 뒤 find(5) 연산을 하면 루트 노드를 탐색하는 과정에서 루트 리스트를 갱신해주기 때문에 경로를 압축해줄 수 있습니다. 이 경우의 시간 복잡도는 O(logN)입니다.