유니온 파인드(Union-find) 알고리즘

1. 유니온 파인드(Union-find) 알고리즘
   • Disjoint Set(서로소 집합)을 표현하기 위해 사용한다 (트리 구조를 활용함)
   • 서로 중복되지 않은 부분집합끼리 연결했을 때 사이클이 생기는지 아닌지를 판단할 수 있는 알고리즘
   • 더욱 간단하게, 노드들이 하나의 집합에 속해 있는지 찾거나, 노드들을 서로 연결하기(합치기) 위해 사용

2. 알고리즘의 구현

• 초기화: n개의 원소를 독립적인 집합으로 구분 초기화
• find 함수: 두 개의 노드가 같은 집합(그래프)에 속하는지 확인하기 위해, 루트(최상위 부모) 노드를 찾는 로직
• union 함수: 두 집합을 하나의 집합으로 합침(두 트리를 하나의 트리로 연결)

3. 시간 복잡도
   • 최악의 경우(아무 규칙 없이 구현할 경우) 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