안녕하세요! 이번 포스트에서는 유니온 파인드(Union-Find) 알고리즘에 대해 알아보고, 이를 활용한 알고리즘 문제를 풀이해 보도록 하겠습니다. 유니온 파인드는 서로소 집합을 관리하는데 매우 유용한 자료구조로, 여러 항목들의 연결 여부를 빠르게 판단하고 집합을 합치는 기능을 제공합니다.
유니온 파인드란?
유니온 파인드는 크게 두 가지 기능으로 구성됩니다:
- Union: 두 원소가 속한 집합을 하나로 합치는 연산
- Find: 특정 원소가 어느 집합에 속하는지 찾는 연산
이 두 운영을 통하여, 우리는 여러 요소 간의 관계를 쉽게 관리할 수 있으며, 복잡한 연결 문제를 효율적으로 해결할 수 있습니다. 특히, 그래프 문제나 네트워크 연결 문제에서 유용하게 사용됩니다.
유니온 파인드의 작동 원리
유니온 파인드는 주로 두 가지 기법을 사용하여 효율성을 극대화합니다:
1. 경로 압축(Path Compression)
Find 연산을 수행할 때, 경로를 압축하여 트리의 높이를 줄입니다. 이를 통해, 여러 번의 Find를 수행할 때 시간 복잡도를 감소시킬 수 있습니다.
2. Union by Rank
Union 연산 시 집합의 ‘랭크(높이)’를 고려하여, 더 낮은 랭크의 집합을 높은 랭크의 집합에 붙입니다. 이 방법 또한 트리의 깊이를 줄여 연산의 효율성을 높입니다.
문제: 연결 요소의 개수 구하기
다음과 같은 문제를 고려해 보세요:
주어진 n개의 노드와 m개의 간선이 있을 때, 서로 연결된 노드 집합의 개수를 구하시오. 노드는 0부터 n-1까지의 정수를 가지며, 간선 정보는 (a, b)의 형태로 주어진다.
입력 예시
5 3
0 1
1 2
3 4
출력 예시
2
해결 과정
이 문제를 해결하기 위해 유니온 파인드 자료구조를 활용하여 각 노드의 관계를 정리할 것입니다. 아래 단계를 따라 진행하겠습니다:
1단계: 부모 배열 초기화
각 노드는 자기 자신을 부모로 가지는 상태로 초기화합니다. 즉, 부모 배열을 생성하고 각 노드가 자기 자신을 가리키도록 설정합니다.
parent = [0, 1, 2, 3, 4] # 노드 수에 맞춰 초기화
2단계: Union 연산 수행
주어진 간선 정보를 기반으로 Union 연산을 통해 노드들을 연결합니다. 이를 통해 서로 연결된 집합을 하나로 묶습니다.
3단계: Find 연산을 통해 연결된 집합 카운팅
각 노드에 대해 Find 연산을 수행하여 어떤 집합에 속하는지를 확인하고, 유일한 루트 노드의 개수를 센 후 결과를 출력합니다.
구현
이제 위의 과정들을 파이썬 코드로 구현해 보겠습니다.
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
self.rank = [1] * size
def find(self, p):
if self.parent[p] != p:
# 경로 압축
self.parent[p] = self.find(self.parent[p])
return self.parent[p]
def union(self, p, q):
rootP = self.find(p)
rootQ = self.find(q)
if rootP != rootQ:
# Union by rank
if self.rank[rootP] > self.rank[rootQ]:
self.parent[rootQ] = rootP
elif self.rank[rootP] < self.rank[rootQ]:
self.parent[rootP] = rootQ
else:
self.parent[rootQ] = rootP
self.rank[rootP] += 1
# 사용 예제
def count_connected_components(n, edges):
uf = UnionFind(n)
# 간선 정보로 Union 수행
for u, v in edges:
uf.union(u, v)
# 유일한 루트의 수를 세어 연결 구성 요소의 개수를 반환
root_set = set(uf.find(i) for i in range(n))
return len(root_set)
# 입력 처리
n = 5
edges = [(0, 1), (1, 2), (3, 4)]
print(count_connected_components(n, edges)) # 출력: 2
결과 해석
위 코드를 실행하면 2라는 결과가 출력됩니다. 이는 주어진 그래프에서 서로 연결된 노드 집합이 두 개 존재함을 의미합니다.
시간 복잡도 분석
유니온 파인드를 사용했을 때, 각 운영의 시간 복잡도는 거의 O(α(n))에 가까워지며, 여기서 α는 아커만 함수의 역함수입니다. 이는 매우 느리게 증가하는 함수이므로, 실제로는 상수에 가까운 시간을 소요한다고 볼 수 있습니다.
마무리
이번 포스트에서는 유니온 파인드 자료구조와 이를 활용한 문제 해결 방법을 살펴보았습니다. 유니온 파인드를 통해 복잡한 연결 문제를 효율적으로 해결할 수 있음을 확인했는데요, 다양한 응용을 해보며 연습해 보시기 바랍니다.
감사합니다!