[알고리즘] 합집합(Disjoint-Set) 찾기, Union-Find 알고리즘

Union-Find(합집합 찾기) 알고리즘은 대표적인 그래프 알고리즘 중 하나로, 서로소 집합(Disjoin-Set)을 표현할 때 사용하는 알고리즘입니다. 그렇다면 Disjoint-Set 이란? Disjoint-Set, 서로소 집합은 공통 원소 없이 나누어진 원소들로 이루어진 부분 집합들에 대한 정보를 저장하고 조작하는 자료구조를 의미합니다. 이렇게 서로소 집합을 표현하기 위한 Union-Find 알고리즘을 구현하기 위해서는 큰 들에서 3가지의 기능을 구현해야 합니다. 초기화: parents 배열을 초기화 (모든 원소가 자기 자신을 부모로 갖도록 배열을 초기화) Union: 두 원소 x, y의 부분 집합을 결합하는 작업 (하나의 서로소 집합으로 합친다.) Find: 해당 원소의 부모를 찾는 작업 (같은 서로소 집합은 같은 부모를 갖는다.) 위와 같이 Disjoint Set 자료 구조를 표현하기 위해서 Union, Find 연산이 필요해서 Union-Find 알고리즘이라고도 불린다고 ...

원문링크 : [알고리즘] 합집합(Disjoint-Set) 찾기, Union-Find 알고리즘