Union-Find, Disjoint Set (유니온-파인드, 상호 배타적 집합)

☞ Union-Find 란? 상호 배타적인 부분 집합(Disjoint Set)들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조 Union-Find에는 자료 구조에 명칭에 맞게 연산이 초기화(init), 합치기(union) 그리고 찾기(find)로 이루어져 있습니다. 초기화 : n개의 원소가 각각의 집합에 포함되어 있도록 초기화 합치기 연산 : 두 원소가 주어질 때 이들이 속한 두 집합을 하나로 합치는 연산 찾기 연산 : 어떤 원소가 주어질 때 이 원소가 속한 집합을 반환하는 연산 ☞ 상호 배타적 집합을 표현하는 방법은 2가지가 있는데, 첫번째는 배열입니다. 하지만 배열로 표현을 하면 합치기 연산에 드는 시간이 많이 걸리기 때문에 Union-Find 자료 구조 특성 상 효율적이지 못합니다. 그..