[4주차] 유니온 파인드 알고리즘

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

 

서로소 집합(Disjoint Set) 자료구조라고도 불리며,
주로 그래프에서 사이클을 판별하거나, 자료들의 연결 정보를 알고 싶을 때 사용

 

핵심

연산	설명
Find(x)	원소 x가 속한 집합의 대표(root)를 찾는다.
Union(a, b)	원소 a가 속한 집합과 b가 속한 집합을 합친다.

 

 

작동원리

1. 초기화 : 각 노드가 자기 자신을 부모로 갖는다.

↓

2. Find 함수 : 루트 노드(대표)를 찾는다

↓

3. Union 함수 : 두 집합을 하나로 합친다

 

# 유니온 파인드 기본 구조 예제

# 1. 초기화: 각 노드가 자기 자신을 부모로 갖는다.
parent = [0, 1, 2, 3, 4, 5]  # 1~5번 노드 예시

# 2. Find 함수 — 루트 노드(대표)를 찾는다.
def find_parent(parent, x):
    if parent[x] != x:               # 부모가 자기 자신이 아니면
        parent[x] = find_parent(parent, parent[x])  # 재귀로 루트를 찾고 경로 압축
    return parent[x]

# 3. Union 함수 — 두 집합을 하나로 합친다.
def union_parent(parent, a, b):
    a = find_parent(parent, a)  # a의 루트 찾기
    b = find_parent(parent, b)  # b의 루트 찾기
    if a < b:
        parent[b] = a           # 작은 번호를 부모로
    else:
        parent[a] = b

# 4. 사용 예시
union_parent(parent, 1, 2)  # 1과 2 합치기
union_parent(parent, 2, 3)  # 2와 3 합치기

# 5. 결과 확인
print(find_parent(parent, 3))  # → 1 (3의 대표)
print(parent)  # 전체 부모 배열 출력 [0, 1, 1, 1, 4, 5]