[알고리즘] 12. Union-Find(합집합 찾기)

1. Union-Find(합집합 찾기)

: 대표적인 그래프 알고리즘. 
서로소 집합(Disjoint-Set)알고리즘이라고도 부름. (* 서로소 : 서로 같은 집합이 아닌것을 찾는 것)
여러 개의 노드가 존재할 때 두개의 노드를 선택해, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘

 

1. 각 부모 노드를 합친다 (더 작은 값을 부모로 갖도록 합침)
2. 같은 부모 노드를 가지는 지 확인 (예) 3이 1을 가리킬 때, 2가 1을 가리키는지 확인하는 함수 사용