- 유니온 파인드(Union-find) 알고리즘
- Disjoint Set(서로소 집합)을 표현하기 위해 사용한다 (트리 구조를 활용함)
- 서로 중복되지 않은 부분집합끼리 연결했을 때 사이클이 생기는지 아닌지를 판단할 수 있는 알고리즘
- 더욱 간단하게, 노드들이 하나의 집합에 속해 있는지 찾거나, 노드들을 서로 연결하기(합치기) 위해 사용
2. 알고리즘의 구현
- 초기화: n개의 원소를 독립적인 집합으로 구분 초기화
- find 함수: 두 개의 노드가 같은 집합(그래프)에 속하는지 확인하기 위해, 루트(최상위 부모) 노드를 찾는 로직
- union 함수: 두 집합을 하나의 집합으로 합침(두 트리를 하나의 트리로 연결)
- 시간 복잡도
- 최악의 경우(아무 규칙 없이 구현할 경우) O(n)
- union-by-rank와 path-compression을 사용할 경우 O(1) => 크루스칼 알고리즘에서도 확인 가능
""" Union-find 알고리즘 """
def find(x):
if x == parents[x]:
return x
else:
p = find(parents[x])
parents[x] = p
return parents[x]
def union(x, y):
x = find(x)
y = find(y)
if x == y:
return
if rank[x] > rank[y]:
parents[y] = x
rank[x] += rank[y]
else:
parents[x] = y
rank[y] += rank[x]
parents = []
rank = []
for i in range(5):
parents.append(i)
# 트리 높이를 고려한다
for i in range(5):
rank.append(1)
union(1, 4)
union(2, 4)
print(parents[1:]) # [4, 4, 3, 4]
print(rank[1:]) # [1, 1, 1, 3]
- 출처 : FASTCAMPUS
댓글