[Algorithm] Union-Find 정리
Union-Find 대표적인 그래프 알고리즘으로 상호 배타적 집합(Disjoint Set)을 표현할 때 사용합니다. 상호배타집합이란? 서로 중복으로 포함된 원소가 없는 집합들을 상호배타집합 혹은 서로소 집합이라 부릅니다. A = {1, 2}, B = {3, 4} = Disjoint Set A = {1, 2}, B = {2, 3, 4} = Not Disjoint Set (2가 중복되기 때문에) 그래프 문제에서 여러 개체를 집합으로 "합치거나" 개체가 어떤 집합에 있는지 "찾을 때" 사용하기 때문에, Union-Find라고 부르며, 이 때 주어진 개체들이 중복된 값을 가지지 않으면 상호배타집합이라 부를 수 있습니다. Union-Find 알고리즘은 단독으로 사용되는 경우는 별로 없고, 다른 알고리즘을 구현하는 과정에서 많이 사용됩니다. 대표적으로 최소비용 신장트리 (MST)를 만드는 크루스칼 알고리즘에서 Union-Find를 이용합니다. 1. Union-Find 연산 Union-Find 지원 연산은 크게 Init(초기화), Union(합치기), Find(찾기) 연산으로 나뉩니다. 위와 같이 여러 개의 개체(노드)가 있다고 가정하겠습니다. Init(초기화) 개체가 어떤 집합에 속해있는지 확인하기 위한 lookup 테이블을 만듭니다. 최초 각 개체는 자기를 제외한 다른 개체들과 집합을 이루지 않기 때문에 자기 자신이 집합의 대표자가 됩니다. 대표자란 각 집합마다 1개씩 있는, Union-Find에서 집합을 구분하는 데 사용되는 원소를 의미합니다. Union (합치기) union(x, y)를 하면 x, y 원소가 속한 2개의 집합을 하나의 집합으로 합칩니다. 여기서 x, y 원소를 합치는게 아니라 x, y가 속한 "집합"을 합친다는 것에 유의해주세요. "집합"을 합치기 위해 초기화 과정에서 생성한 lookup 테이블의 "대표자"를 이용합니다.