[D-15] 유니온 파인드

📍 유니온 파인드

✅ 정의

유니온 파인드(union-find)는 일반적으로 여러 노드가 있을 때
특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과
두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘을 말한다.

 

✅ 핵심 이론

union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산이다.
                    노드 a, b가 a ∈ A, b가 b ∈ B일 때 union(a, b)는 A∪B를 말한다.

 

find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다. 
                    노드 a가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환한다.