이름을 들으면 뭔지 잘 모르겠는 disjoint...Set..? 과 Union-Find..?
파헤쳐보자.
disjoint Set은 '서로소 집합'으로
공통 원소를 갖지 않는 2개 이상의 집합을 의미한다.
(왼쪽은 1이라는 공통원소를 가지고 있으므로 서로소 관계가 아니다.)
그래서 보통 이 자료구조를 사용해서 서로소 여부 판단 및 합집합을 사용할때 주로 사용한다. 이때 사용되는 연산이 MakeSet, Union, Find이다.
이것을 구현한다면,
int[] set = new int[5];
for(int i=0; i<4; i++) {
set[i] = i; // 자기 자신을 가리키도록 초기화한다.
}
이렇게 할 수 있다.
원소가 어떤 집합에 속해있는지 말하려면 그 집합의 대표자를 알아야한다. 그래야만 "나는 1(대표자)의 집합에 속해있다!!!"라고 할 수 있다.
그래프에서는 대표자라는 용어 대신 "부모"라고 표현한다.
그리고 그 집합의 부모노드가 갖는 특징은 "노드가 자기 자신을 가리키고 있다"는 특징을 가지고 있다.
MakeSet에서 구현한 그래프 정보를 조금 수정해서
set[0] = 1; // 0번 노드는 1번 노드를 가리킨다.
set[2] = 3; // 2번 노드는 3번 노드를 가리킨다.
set[3] = 4; // 3번 노드는 4번 노드를 가리킨다.
이것을 실행하면,
위의 그림과 같이 A집합의 부모노드는 1이며 B집합의 부모노드는 4가 된다.
이 그래프를 바탕으로 이제 어떤 원소가 속한 집단(부모노드)가 누구인지를 찾아줘야한다. 이 연산이 바로 Find 연산이다.
부모노드의 특징인 "자기 자신을 가리킨다"를 이용하면 찾을 수 있다.
public static int find(int[] set, int i) {
if(set[i] == i) { // 해당 노드가 가리키는 것이 자기 자신이라면
return i; // 부모 찾았다!!! 부모 노드 리턴!!
}
return find(set, set[i]); // 에헤이~ 이 노드도 다른 노드를 가리키고 있네,
그 노드는 뭐하는 노드길래~ 한번 찾아가보자.
}
이렇게 부모 노드를 찾는 코드를 작성할 수 있다.
"두개의 집합을 합친다."
이것의 의미는 1(대표)의 집합과 4(대표)의 집합을 합친다는 의미로,
어느 한 집단의 대표는 2명이 될 수 없듯이, 합치려면 부모 노드는 1개여야만한다. 따라서 한 집합이 다른 집합에 귀속이 되어야한다.
이것은 대표끼리 협상하는것으로, 하나의 부모 노드가 다른 부모노드를 가리키게만 하면된다.
set[4] = 1;
위 그림과 같이 4(부모)가 1(부모)를 가리키게하면서 1집합에 합쳐졌다.
(ps. 어느 쪽으로 합치는지는 방식이 여러가지 있다. 다음편 포스팅)
이것은 0의 부모를 찾아주고, 3의 부모를 find로 찾아서,
대표끼리 union해주면 해결할 수 있다.
// v1와 v2가 속한 서로 다른 집합을 합친다.
public static void union(int[] set, int v1, int v2) {
// 먼저 v1,v2가 속한 집단(부모)을 찾는다.
int a_parent = find(set, v1);
int b_parent = find(set, v2);
// 어느쪽으로 합칠 지 기준은 간단히 원소값으로 판단했다.
if(a_parent < b_parent) {
set[b_parent] = a_parent;
} else {
set[a_parent] = b_parent;
}
}
public static int find(int[] set, int v) {
if(set[v] ==v ) {
return v; // 부모 찾았다.
}
return find(set, set[v]); // 부모가 아니다. 가리키는 노드 넘어가서 찾아보자.
}
이렇게 하면 disjoint Set(서로소)관계인 집합을 Union-Find 연산을 사용해서 합칠 수 있다.
이번 편을 공부하면서 Union-Find 최적화에 대해 알게되었다.
다음편은 그녀석을 파헤쳐보자.