Union Find 알고리즘 | 개념과 Python 코드 구현

안녕하세요. 오늘은 백준의 친구 네트워크 문제를 풀면서 알게 된 union-find 알고리즘에 대해 글을 작성해보려 합니다.

 

📌 Union Find 알고리즘이란?

Union Find 알고리즘은 서로소 집합(Disjoint Set)을 표현할 때 사용하는 알고리즘입니다. 집합을 표현하는 자료구조로 배열, 연결 리스트 등을 활용할 수 있겠지만, 트리 구조가 집합 표현에서는 가장 효율적입니다. 따라서 Union set 알고리즘도 트리 구조를 사용하는 그래프 알고리즘으로 볼 수 있습니다. 

 

서로소 집합은 서로 중복되지 않는 부분 집합을 의미합니다.

예를 들어, {1, 2}와 {2, 3}은 2라는 중복되는 원소가 있으므로 서로소 집합이 아니지만, {1, 2}와 {3, 4}는 서로 중복되는 원소가 없으므로 서로소 집합입니다.

 

📌 Union Find 자료구조로 서로소 집합 표현하기

이런 서로소 집합을 트리 구조로 표현하면 어떻게 표현될까요?

예를 들어, {1, 2, 3}, {3, 4}, {5, 6} 이렇게 3개의 집합이 있을 때 이 집합들을 union-find 자료구조로 표현하면 아래처럼 트리로 표현할 수  있습니다. 숫자가 더 큰 노드일 수록 더 아래쪽에 배치하였습니다. 

 

📌 알고리즘 구현하기 (Python)

Union Find 알고리즘을 구현하기 위해서는 3단계가 수행되어야 합니다. 

1. Initialize
   첫번째 단계는 초기화입니다. 이 단계에서는 하나의 원소를 유일하게 가지는 각각의 집합을 만듭니다. 즉, 초기화 단계에서는 원소의 개수만큼 집합이 만들어집니다.
2. Union
   두번째는 두 노드가 속한 집합을 합치는 연산을 하는 단계입니다. 이 연산을 하기 위해서는 두 노드가 속한 집합을 찾는 과정이 필요합니다. 그 과정이 아래의 Find 입니다.
3. Find
   Find에서는 노드의 루트노드를 찾습니다. 우리는 노드의 루트 노드를 그 집합의 대표값으로 취급합니다. 따라서 루트 노드를 찾는 것이 그 노드가 속해있는 집합을 찾는 것으로 볼 수 있습니다.

그럼, 이 3가지 과정을 직접 파이썬으로 구현해보겠습니다. 

# -*- coding: utf-8 -*-
# Union Find Algorithm


def init(n):
	parent = [i for i in range(n + 1)]
	return parent

def find(x):
    if parent[x] != x:
        return find(parent[x])
    return x

def union(x, y):
	x = find(x)
	y = find(y)

	if x > y:
		parent[x] = y
	else:
		parent[y] = x

init 함수에서는 원소의 개수, n에 따라 parent 리스트를 초기화해줍니다. 즉, 1의 루트 노드는 1, 2의 루트 노드는 2 이렇게요!

그리고 find 함수에서는 재귀를 통해서 부모를 타고 타고 최종적으로 루트 노드에 도달할 수 있도록 합니다.

union에서는 두 노드의 루트 노드를 찾아서 더 작은 루트 노드를 큰 노드의 부모 노드로 연결해 줍니다.

 

parent = init(5)

union(1, 4)
union(4, 2)

print(parent)

위의 코드를 실행하여 보면 [0, 1, 1, 3, 1]가 출력됩니다! 즉, 1, 2, 4가 같은 집합에 속한 다는 것을 알 수 있습니다.

 

📌 시간복잡도

위 코드의 시간복잡도를 계산하여 봅시다. 전체 알고리즘은 결국 find 함수의 시간복잡도에 의존하게 됩니다. find 알고리즘은 재귀적으로 돌아가는데, 최악의 경우는 완전히 편향된(skewed) 트리 모양일 때입니다.

skewed tree

이 때는 노드의 개수가 $N$일 때, 최종 루트 노드를 찾는 시간복잡도가 $O(N-1)$입니다. 파이썬의 경우에는 노드가 1000개 이상일 때, 최악의 경우 재귀가 1000번 이상을 돌면 RecursionError가 발생할 확률이 높습니다.(파이썬에서는 시스템의 안정을 위해 재귀의 한도가 정해져 있기 때문이지요. 이 한도를 늘릴 수는 있지만, 시간복잡도를 줄이는 쪽이 훨씬 더 좋은 알고리즘이라고 할 수 있겠죠?ㅎㅎ) 바로 아래처럼요!(ㅎ_ㅎ;;)

바로 이렇게요!

 

📌 경로 압축 (Path Compression)

따라서 우리는 find 함수의 시간복잡도를 줄여야 합니다! 어떻게요? 경로 압축을 통해서요! 즉, find 하면서 만난 모든 값의 부모 노드를 root로 만듭니다. find 연산을 재귀적으로 하면 루트노드까지 모든 부모 노드를 방문하게 되는데, 방문할 때마다 그 부모 노드의 부모 노드를 자신의 부모 노드로 만들어 최종적으로는 모든 원소가 루트 노드로 연결되도록 하는 방법입니다.

 find 함수를 아래 코드처럼 수정해봅시다.

def find(x):
    if parent[x] != x:
    	parent[x] = find(parent[x])
        return parent[x]
    return x

경로 압축을 진행하면 find를 할 때마다 트리의 깊이가 달라집니다. (트리가 훨씬 평평해집니다.)

find를 수행할 때마다 해당 노드의 부모 노드를 바꿔주기 때문에 트리의 깊이가 아래처럼 점점 줄어들게 되는 거죠! 이렇게 하면 시간복잡도는 $O(logN)$으로 줄일 수 있습니다. 

모든 원소가 루트 노드로 연결됩니다.

 

📌 Union Find 알고리즘을 활용하는 문제

BAEKJOON #4195) 친구 네트워크 | union-find | Python

 

📚 참고한 페이지

[알고리즘] union-find 알고리즘

[알고리즘] 유니온파인드(Union-Find) 알고리즘

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