disjoint Set과 Union-Find 파헤치기

이름을 들으면 뭔지 잘 모르겠는 disjoint...Set..? 과 Union-Find..?
파헤쳐보자.

 

개념

disjoint Set은 '서로소 집합'으로
공통 원소를 갖지 않는 2개 이상의 집합을 의미한다.

(왼쪽은 1이라는 공통원소를 가지고 있으므로 서로소 관계가 아니다.)

 

MakeSet, Union, Find

1) MakeSet : 모든 원소들을 각각 독립적인 집합으로 만든다.

이것을 구현한다면,

int[] set = new int[5];
for(int i=0; i<4; i++) {
set[i] = i; // 자기 자신을 가리키도록 초기화한다.
}

이렇게 할 수 있다.

 

2) Find : 원소가 어떤 집합에 속해있는지 찾는다.

원소가 어떤 집합에 속해있는지 말하려면 그 집합의 대표자를 알아야한다. 그래야만 "나느 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]); // 에헤이~ 이 노드도 다른 노드를 가리키고 있네, 
그 노드는 뭐하는 노드길래~ 한번 찾아가보자.
}

이렇게 부모 노드를 찾는 코드를 작성할 수 있다.

 

3) Union : 서로 다른 두개의 집합을 합친다.

이것의 의미는 1(대표)의 집합과 4(대표)의 집합을 합친다는 의미로,
어느 한 집단의 대표는 2명이 될 수 없듯이, 합치려면 부모 노드는 1개여야만한다. 따라서 한 집합이 다른 집합에 귀속이 되어야한다.
이것은 대표끼리 협상하는것으로, 하나의 부모 노드가 다른 부모노드를 가리키게만 하면된다.

set[4] = 1;

위 그림과 같이 4(부모)가 1(부모)를 가리키게하면서 1집합에 합쳐졌다.
(ps. 어느 쪽으로 합치는지는 방식이 여러가지 있다. 다음편 포스팅)

 

활용

"원소0"이 속한 집합과 "원소3"이 속한 집합을 합쳐라.

이것은 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 최적화에 대해 알아보자.