[JAVA] 서로소 집합(Disjoint Sets)과 연산(Union & Find)

서로소(Disjoint) 서로소(disjoint)는 공통으로 포함하는 원소가 없는 두 집합의 관계다. 서로소 집합(Disjoint Sets)과 연산(Union & Find) 서로소 집합은 위 그림처럼 서로소 집합끼리 나눠진 원소를 처리하기 위한 자료구조이다. 서로소 집합은 크게 두 가지 연산을 기반으로 구현된다. Union : 서로 다른 두 개의 집합을 병합한다. Find : 원소가 어느 집합에 속해있는지 찾는다. 그렇다면 어느 집합에 속해있는 지는 어떻게 판단할까? 원소 1, 2, 3, 4가 있을 때, 각 원소가 가리키는 대상의 '집합'이 자신이 속한 '집합'이라고 간주한다. 따라서 원소 2가 1을 가리키고 있다면, 원소 2는 1의 집합에 속한 원소라고 할 수 있다. 서로소 집합의 두 연산을 빗대 Un..

2022.03.02