[자료구조] Union-find

Union-find

- Disjoint Set을 표현할 때, 활용하는 알고리즘으로 트리를 이용합니다.

- Disjoint Set이란 서로 중복되지 않는 부분 집합들로 이뤄진 원소들의 정보를 저장하는 자료구조로 서로 공통 원소가 없는 부분 집합들을 뜻합니다.

- 해당 알고리즘은 기본적으로 3가지 연산을 이용합니다.

 

1. make-set(x)

: '초기화' 메서드로 x를 유일한 원소로 갖는 집합(트리)를 생성합니다.

 

2. union(x, y)

: x가 속한 집합과 y가 속한 집합을 합칩니다.(합집합)

 

3. find(x)

: x가 속한 집합(트리)의 루트값을 반환합니다.

 

www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

int[] tree = new int[n+1];
for(int i=1; i<n+1; i++) {
    tree[i] = i;
}

public void union(int ele1, int ele2) {
    ele1 = find(ele1);
    ele2 = find(ele2);

    // 트리의 루트노드 변경
    if(ele1 != ele2) {
        tree[ele2] = ele1;
    }
}

public int find(int ele) {
    if(tree[ele] == ele) {
        return ele;
    } else {
        // Tree 경로 압축, O(logN)
        return tree[ele] = find(tree[ele]);
    }
}

 1차원 행렬 tree에는 각 노드별로 루트 노드가 저장돼있습니다. make-set(i)을 하기위해 각 노드별 자기 자신을 루트로 초기화했습니다. 

 

 이제 루트노드를 찾는 재귀함수 find부터 살펴보면, tree[ele] == ele인 경우, ele를 반환합니다. 이 뜻은 아직까지 해당 노드가 다른 집합에 속하지 않는다는 뜻으로 자기 자신이 루트임을 의미합니다. else 문의 경우, tree[ele] = find(tree[ele])를 통해 재귀를 진행하면서 각 노드의 루트 노드를 갱신하는 과정입니다.

 

 union은 먼저, ele1과 ele2 각각의 루트노드를 find를 통해 구합니다. 다음으로 두 루트값을 이용해 만약 서로의 루트 노드가 다르다면 ele2의 집합을 ele1에 속해준다는 의미로 tree[ele2]에 ele1을 저장합니다. 이렇게 배열을 갱신하면 나중에 find를 호출했을 때, ele2의 루트와 ele1의 루트가 같은 결과가 나오게 됩니다.