[JAVA] Quick Union

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요 ;)

---

이전 포스팅에서 다뤘던 Quick Find 알고리즘은 union 연산에 있어서 모든 배열에 한 번씩 접근을 해야 하기 때문에 시간 비용 측면에서 매우 비싸고expensive 비효율적이라는 사실을 확인했습니다.

이번 포스팅에서는 그 union 연산을 조금 더 효율적으로 처리할 수 있는 Quick Union 알고리즘에 대해 알아보겠습니다.

 

Quick Union 알고리즘은 루트(root)라는 개념을 사용합니다. union 연산을 처리할 때 연결된 모든 멤버들에 접근하여 값을 변경하는 것이 아니라, union 연산을 통해 연결을 할 때 자식 노드로 멤버를 저장시키고 자신은 root가 되는 방식입니다.

 

이 그림을 보면 Quick Union 알고리즘이 Quick Find 연산보다 효율적인 이유를 알 수 있습니다. Quick Find 알고리즘에서 3과 5를 연결시키려면 3과 연결된 2, 4, 그리고 9의 값을 전부 인덱스 5의 배열 값으로 변경해줘야 합니다. 하지만 Quick Union 알고리즘에서는 3의 최종 root인 인덱스 9의 배열 값을 6으로 바꿔주면 됩니다. 3과 연결된 최종 루트 하나의 값만 변경해주면 union 연산이 종료됩니다.

그림1

그림2

위의 두 그림처럼, Quick Union 알고리즘에서의 union 연산은 모두 최종 root를 기준으로 이뤄집니다. 

 

그림1에서 union(9,4) 연산은 4가 9의 부모 root가 됨으로써 연결이 되는 구조인데, 4의 최종 root는 8이기 때문에 9가 8의 자식 노드로 들어가기만 하면 되고, 9를 제외한 나머지 노드들의 값이 변경될 필요가 없습니다.

 

그림 2 역시 union(6,1)을 통해 1이 6의 부모 root가 되어야 하는데, 6의 최종 root는 0이기 때문에 인덱스 0의 배열 값만 1로 변경하면 나머지 배열의 변경 없이 1과 6의 union이 이뤄집니다.

public class QuickUnion {
    private int[] id;

    public QuickUnion(int N){
        id = new int[N];
        for(int i=0; i< N; i++){
            id[i] = i;
        }
    }

    private int root(int i){
        while(i!=id[i]) i = id[i];  // 부모 root를 불러냄
        return i;
    }

    public boolean connected(int p, int q){
        return root(p) == root(q);
    }

    public void union(int p, int q){
        int i = root(p);
        int j = root(q);
        id[i]= j;
    }
}

이 코드가 Quick Union의 구현 코드입니다. Quick Find에 비해 for 루프를 돌지 않기 때문에 코드의 길이도 전반적으로 짧고, 연산에 필요한 시간 역시 짧습니다.

하지만 루트를 연결한 트리가 세로로 길게 이어져있을 때 그 트리를 거슬러 올라가는 연산이 증가할 수 있다는 게 Quick Union의 결함입니다.