유니온 파인드 (Union-Find)

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

출처 : https://jojozhuang.github.io/algorithm/algorithm-union-find/

Union-Find 과정

1. 최초 노드는 자기자신을 루트노드로 가짐
2. Union(x, y) : x가 속한 집합과 y가 속한 집합을 합침
   1. 대표 노드를 설정하고 자식이 되는 노드의 값을 대표 노드의 값으로 변경
3. Find(x) : x가 속한 집하의 root 노드를 반환
   1. 대상 노드 배열에 index 값과 value값이 동일한지 확인
   2. 동일하지 않으면 value값이 가리키는 index 위치로 이동
   3. 이동 위치의 index값과 value값이 같을 때까지 1~2번 반복
   4. 대표 노드에 도달하면 대표 노드로 도달하기 까지의 모든 노드들의 값을 루트 노드값으로 변경

Find 연산을 이용하게 되면 모든 노드가 루트 노드에 직접 연결되는 형태로 변경이 되게 됩니다. 그럼으로써 루트 노드를 Find 할 때 경로가 압축이 되는 효과를 얻을 수 있게 됩니다.

 

Unoin-Find를 이용한 알고리즘 문제

[알고리즘] 백준 1717 : 집합의 표현 - JAVA