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

Ⅰ. '유니온-파인드' 알고리즘이란?

1. 뜻 : 상호 배타적 집합에서의 병합 연산과 탐색 연산. 1) 상호 배타적 집합(Disjoint Set) == 서로소 집합 : 교집합이 없는 집합. 2.

순서 : Find 연산(두 노드의 루트 찾기) → Union 연산(두 노드의 루트 中 1개로 루트 통일하기) Ⅱ. 유니온(Union) : 병합(= 합치기) 1.

뜻 : 두 노드가 속한 '집합'을 '하나'로 합치는 연산. 2. 분류 : 집합 알고리즘에서의 연산. 3.

방법 : 두 집합의 루트 中 1개로 루트를 통일시킴. 1) 해설 : 한 집합의 루트의 부모 노드 부분을 다른 한 집합의 루트 값으로 바꿈. (1) 예시 : 집합 A의 루트가 1이고, 집합 B의 루트가 2일 때, 이 둘을 집합 B를 기준으로 병합할 경우. ① 기존 <1> 집합 A의 1번 노드(루트)의 부모 노드 값 : 1 <2> 집합 B의 2번 노드(루트)의 부모 노드 값 : 2 ② 루트 통일 후 <1> 집합 A의 1번 노드의 부모...