Union-Find 연산의 성능 개선

Union-Find 연산의 성능 개선

어떤 요소들이 하나의 그룹으로 구성될 수 있는지 파악하기 위한 Disjoint-Set 자료구조를 처리하기 위해 Union-Find 연산을 사용한다.

이번 post에서는 union-find 연산의 성능 개선을 위한 path compression과 rank 활용에 대해 알아보자.

기본 코드는 다음과 같다.

package ch07_unionfind;

import java.util.Arrays;

public class P01_UnionFindTree {
    static int[] src = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    static int[] repres = new int[src.length + 1];

    // 각각의 멤버를 대표자로 하는 집합 생성
    static void makeSet() {
        for (int i = 0; i < src.length; i++) {
            repres[src[i]] = src[i];
        }
    }

    // x가 속한 그룹의 대표를 찾는다.
    static int findSet(int x) {
        // repres의 값과 x가 같다면 내가 대표
        if (repres[x] == x) {
            return x;
        }
        // 그렇지 않다면 대표를 통해 다시 대표 확인
        else {
            return findSet(repres[x]);
        }
    }

    static void union(int x, int y) {
        // 각각 대표자를 데려온다.
        x = findSet(x);
        y = findSet(y);
        // 두 요소가 속한 그룹의 대표가 같다면 이미 같은 집합
        if (x == y) {
            return;
        }
        // 그렇지 않은 경우 한 녀석의 대표자를 다른 녀석으로 대체
        else {
            repres[y] = x;
        }
    }

    public static void main(String[] args) {
        makeSet();

        System.out.printf("처음 대표자 구성: %s%n", Arrays.toString(repres));
        for (int i = 0; i < src.length - 1; i++) {
            union(src[i], src[i + 1]);
        }
        System.out.printf("최종 대표자 구성: %s%n", Arrays.toString(repres));
    }
}

 

union-find 연산의 문제점

disjoint set 자료구조는 그룹의 대표자를 링크로 연결해서 참조하는 구조이다.

즉 위와 같은 구조에서 4의 대표자는 1이다. 이 과정에서 단순히 findSet 연산을 아래와 같이 수행할 수 있다.

// x가 속한 그룹의 대표를 찾는다.
static int findSet(int x) {
    // repres의 값과 x가 같다면 내가 대표
    if(repres[x]==x) {
        return x;
    }
    // 그렇지 않다면 대표를 통해 다시 대표 확인
    else {
        return findSet(repres[x]);
    }
}

문제는 4가 대표자를 찾을 때 3의 대표자를 거쳐 2의 대표자를 거쳐 1을 찾는과정이다. 경로가 늘어질 경우 대표를 찾는데 많은 연산이 필요하게 된다. 찾고싶은것은 대표자이지 경로가 아니다.(집합이기 때문에 경로는 당연히 무의미하다.)

이를 개선시키는 방법은 좀 더 빨리 대표자를 찾게 하기 위해 경로를 단순화 시키는 것이다.

즉 위와 같은 참조 경로를 만들어준다면 4의 대표를 찾는데 1번의 연산만으로 처리가 가능하다. 

이를 어떻게 구현할 것인가?

 

rank 활용

 

rank  활용

각 노드 별로 자신을 루트로 하는 subtree의 높이를 별도의 배열로 관리하며  union 과정에서 활용된다.

static int[] rank = new int[src.length + 1];

 

두 대표자의 랭크가 다른 경우

두 대표자의 랭크가 다른 경우는 union 과정에서 작은 녀석을 큰 녀석에게 붙여주면 된다. 그러면 전체적으로 rank의 변화는 발생하지 않는다.

 

두 대표자의 랭크가 같은 경우

두 대표자가 다른 경우는 한 그룹의 대표자 랭크를 임의로 1 증가시켜준다. 그렇게 되면 다시 위의 경우와 마찬가지로 랭크가 다른 경우가 된다.

 

구현 코드

static void union(int x, int y) {
    // 각각 대표자를 데려온다.
    x = findSet(x);
    y = findSet(y);
    // 두 요소가 속한 그룹의 대표가 같다면 이미 같은 집합
    if (x == y) {
        return;
    }
    // 그렇지 않은 경우 한 녀석의 대표자를 다른 녀석으로 대체
    else {
        // 랭크가 같아면 한 녀석을 그냥 높여준다.
        if (rank[x] == rank[y]) {
            rank[x]++;
        }
        // 합치는 과정에서 rank가 낮은 녀석을 높은 녀석에게 붙여준다.
        // a의 랭크가 더 높다면.. b의 대표자를 a로 변경
        if (rank[x] > rank[y]) {
            repres[y] = x;
        }
        // b의 랭크가 더 높다면 a의 대표자를 b로 변경. 혹시 같았다면 b를 높여주면됨
        else {
            repres[x] = y;
        }
        repres[y] = x;
    }
}

 

path compression

 

기존 findSet의 문제점

기존의 findSet은 깊이가 깊어지면서 대표자를 찾는 과정에서 시간이 오래 걸린다.

위와 같은 경우 4의 대표를찾으려면 3의 대표, 2의 대표를 쭉 찾아 올라가야 한다. 깊이가 깊어질 수록 재귀를 타는 시간이 증가한다.

경로 단축을 통한 호출 절약

사실 우리에게 필요한 것은 경로가 아닌 대표자이다. 따라서 findSet 과정에서 모든 노드들이 직접 대표자를 가리키도록 변경해주자.

이제 경로를 타고 탐색하지 않고 바로 대표자를 추출 할 수 있게 되었다.

구현 코드

// x가 속한 그룹의 대표를 찾는다.
static int findSet(int x) {
    // repres의 값과 x가 같다면 내가 대표
    if(repres[x]==x) {
        return x;
    }
    // 그렇지 않다면 대표를 통해 다시 대표 확인
    else {
        return repres[x] = findSet(repres[x]);
    }
}

 

같이 사용할 필요는 ??

최고의 성능을 내고 싶다고 rank와 path compression을 함께 사용하는것이 유용할 지는 고민할 필요가 있다. path compression 을 거치게 되면 rank에 대한 변경도 필요한데 이 연산까지 처리하기에는 too much일 수 있기 때문이다.

대부분 path compression 코드가 간단하기 때문에 이를 활용하는 것이 일반적이다.