[Algorithm] 유니온 파인드 (Union-Find) : Disjoint-set 표현

인트로 Union-Find 알고리즘은 서로소 집합*(Disjoint-set)을 표현하는 그래프 알고리즘으로 임의의 두 노드(원소)가 서로 같은 그래프(집합)에 속하는지 판별하는 알고리즘이다. 여기엔 핵심이 되는 두 가지 연산이 존재한다. Union : 원소 x가 포함된 집합과 원소 y가 포함된 집합을 하나로 합치는 연산 Find : 원소 x가 포함된 집합을 반환하는 연산 참고로 Union-Find 알고리즘은 최소 신장 트리(MST)를 구하는 크루스칼 알고리즘에 사용된다. 서로소 집합 (Disjoint-set)이란? 공통 원소가 없는 두 집합을 서로소 집합이라 한다. A = { 1, 2 ,3 } B = { 5, 7, 9 } 집합 A와 B는 서로소 집합이다. A = { 3, 5 ,7 } B = { 7, 9,..