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

서로소(Disjoint)

 

서로소(disjoint)는 공통으로 포함하는 원소가 없는 두 집합의 관계다.

 

 

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

 

서로소 집합은 위 그림처럼 서로소 집합끼리 나눠진 원소를 처리하기 위한 자료구조이다.

서로소 집합은 크게 두 가지 연산을 기반으로 구현된다.

• Union : 서로 다른 두 개의 집합을 병합한다.
• Find : 원소가 어느 집합에 속해있는지 찾는다.

그렇다면 어느 집합에 속해있는 지는 어떻게 판단할까?

원소 1, 2, 3, 4가 있을 때, 각 원소가 가리키는 대상의 '집합'이 자신이 속한 '집합'이라고 간주한다.

따라서 원소 2가 1을 가리키고 있다면, 원소 2는 1의 집합에 속한 원소라고 할 수 있다.

 

서로소 집합의 두 연산을 빗대 Union-Find 자료구조라고도 불린다.

 

 

 

서로소 집합의 구현 - 집합 생성 및 초기화

 

개념을 어느 정도 짚고 넘어갔다면, 서로소 집합과 연산을 코드로 구현해보자.

 

0~4까지의 원소를 각각 가진 5개의 서로소 집합이 있다고 가정해보자. 

처음 서로소 집합을 만들 때는, 자기 자신을 집합의 부모라고 간주한다.

즉, 0은 부모가 0인 집합, 1은 부모가 1인 집합.....4는 부모가 4인 집합에 속해있는 상태다.

 

해당 그림을 코드로 구현해보면 왼쪽과 같다.

각 set의 인덱스는 자기 자신을 가리키고 있음

 

 

 

이제 find와 union연산을 위해 집합을 두 그룹으로 나누어보자.

 

A 집합은 2가 집합의 부모이며(자기 자신을 가리킴), 속한 원소는 [1, 2]이다.

B 집합은 5가 집합의 부모이며, 속한 원소는 [3, 4, 5]이다.

 

 

 

서로소 집합의 구현 - Find 함수

자, 이제 자신이 속한 집합을 찾는 find 연산을 코드로 구현해보자!

 

필자는 편의상 집합을 A와 B로 라벨링 했지만, 한 원소가 속한 집합이 어떤 집합인지 코드로 표현하는 방법은 다르다. 코드에서는 자신이 속한 집합의 대표로 집합을 구분하고, 그 대표를 통상적으로 '부모'라고 한다.

부모는 'index 와 index가 가리키는 값이 일치하는 원소'이다.

 

A 집합의 경우, set[0] = 1이고, set[1] = 1 자기 자신이므로 1이 집합A의 부모다.

B 집합의 경우, 2의 부모를 찾기 위해 set[2]값을 보면 3이다. 허나 3은 set[3] = 4로 자기 자신을 가리키고 있지 않으니 '같은 집합이지만 2의 부모는 아닌 셈이다.' 3이 가리키는 set[4] = 4로 자기 자신을 가리키고 있으니 원소 4가 B 집합의 부모이며, 2와 3이 속한 집단은 4(부모)라고 간주할 수 있다.

 

find 함수를 구현한 코드다.

재귀함수라 조금 헷갈린다면 필자가 위에 B집합에서 2의 부모를 찾는 과정을 그대로 코드에 대입해 따라가보면 좀 수월할 것이다.

 

 

 

 

 

서로소 집합의 구현 - Union 함수

 

이제 A, B 집합을 합쳐보자!

두 집합을 합칠 때, 어느 쪽으로 합칠지의 여부는 필자의 경우 원소 값이 더 작은 쪽으로 합치는 방식을 택했다. 따라서 A와 B를 합치는 경우, B의 집합을 모두 A의 집합으로 넣을 것이다.

아까 집합을 구분짓는 것은 각 집합의 '부모'원소라고 했으니, B 집합의 부모를 A집합의 부모로 교체해주면 된다.

 

 

1. 매개변수로 합칠 원소 두 개를 받는다.

2. 각 원소의 집합을 대표하는 부모를 가져온다.

3. 부모의 대소 비교에 따라 어느 쪽으로 합칠지 결정하면 끝이다!

 

 

 

따라서 위의 메소드를 거쳐간 집합들의 상태는 아래와 같아진다.

find(set, 3, 1) : 3이 속한 집합과 1이 속한 집합을 합친다.

이렇게 서로소 집합과 Find & Union연산을 살펴보았다.

이 개념은 무방향 그래프의 사이클 여부를 판단하거나 최소 비용 신장 트리를 만들기 위한 '크루스칼 알고리즘'에 기본 바탕이 되므로 숙지해두면 도움이 될 것이다.

따라서 다음 포스팅은 '크루스칼 알고리즘'에 대해 다뤄보도록 하겠다!