[AL] 6. Union-Find 알고리즘
6. Union-Find 알고리즘 Union-Find Union-Find 구현 최적화 (Optimization) 1. Union-Find 1.1. Union-Find 란? 서로소 집합(Disjoint Set) 라고 불리며, Union(x,y) 과 Find(x) 연산을 수행한다 Union(x,y) 를 수행하면 x와 y는 같은 집합에 속하게 되며, Find(x) 와 Find(y) 는 x, y 가 같은 집합에 속할 때만 같은 값을 가진다. 따라서, 전체 요소들을 서서히 묶어나가는 상황에서 유용하게 사용할 수 있는 자료구조이다. 1.2. 원리 배열을 이용해서 Tree 자료구조를 만들어 구현하며, 최상단 노드를 Root 노드로 하여 집합을 구분한다 주어진 두 원소 또는 집합을 합하는 Union 부분과 원소가 어떤..