Union - Find 알고리즘

유니온 파인드 알고리즘은 상호 배타적 집합(Disjoint-set)이라고도 한다.

아래 세 가지 연산으로 이루어짐

 

 

1. 초기화

parent=[i for i in range(5)]

1차원 배열을 사용해서 n개의 원소가 서로 다른 집합에 속하도록 한다.

i의 부모 노드는 parent[i]

 

 

2. Find

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

노드 x가 어느 집합에 속하는지 찾는 연산(=x의 루트 찾기)

x==parent[x]면 x가 부모 노드

그렇지 않다면 재귀 호출을 사용해 루트를 찾아 반환

아래는 find 함수를 최적화한 코드

 

def find(a) :
    if a == parent[a] :
        return a
    parent[a]=find(parent[a])   # 경로 압축
    return parent[a]

 

경로 압축을 한 find 함수

a의 루트를 저장해두면 찾기 연산의 중복을 피할 수 있음.

 

 

3. Union

def union(a, b) :
    a=find(a)
    b=find(b)
	
    if a != b :
    	if b < a :
        	parent[a]=b
    	else :
        	parent[b]=a

 

노드 a가 속한 집합과 노드 b가 속한 집합을 합치는 연산

find 함수를 통해 찾은 a와 b의 루트 노드의 값을 비교한다.

높이가 더 낮은 트리를 더 높은 트리 밑에 넣어서 합친다.

parent[a]=b는 b가 a의 부모임을 뜻한다.

이렇게 하지 않으면 한 쪽으로 트리가 기울어질 수 있고 O(n)이 될 것이다.

 

 

👧 관련 알고리즘 문제

1. 백준 1197 최소 스패닝 트리 https://www.acmicpc.net/problem/1197

 

 

 

 

참고 👉 https://ssungkang.tistory.com/entry/Algorithm-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9CUnion-Find

[Algorithm] 유니온 파인드(Union - Find)

 

프로그래밍 대회에서 배우는 알고리즘 문제해결전략