[JAVA] Quick Union Improvements

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

---

저번 포스팅에서 다뤘던 Quick Union은 Quick Find에 비해 union 연산이 빠르다는 장점을 다뤘지만, 트리의 크기가 커질 수 있다는 단점을 가지고 있었습니다. 이번 포스팅에서는 Quick Union에서 트리의 크기에 따라 발생할 수 있는 문제를 해결하는 알고리즘에 대해 알아보겠습니다.

---

루트로 가는 평균 거리가 훨씬 짧아짐

첫 번째 개선 알고리즘은 Weighted 알고리즘입니다. 이 알고리즘은 union 연산에서 트리를 만들 때, union 연산에서 매개변수로 받는 인자들의 순서에 관계 없이, 더 작은 트리를 가진 쪽이 더 큰 트리를 가진 쪽의 자식 노드로 들어가는 방법입니다. 이를 통해 크기가 큰 트리가 작은 트리의 자식 노드로 들어가 트리의 크기가 커지는 걸 방지할 수 있습니다.

---

public class WeightedQuickUnion {
    private int[] id;
    private int[] sz;

    public WeightedQuickUnion(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);
        if(i==j) return;
        if(sz[i]<sz[j]){id[i]=j; sz[j]+=sz[i];}	// size가 작은 배열이 size가 큰 배열 밑으로
        else {id[j]=i; sz[i] += sz[j];}		// size배열의 수정도 바로 해줘야 함
    }
}

---

연산 시간이 효과적으로 감소

위의 그림들에서 말하고자 하는 건, weighted Quick Union 알고리즘이 이전의 알고리즘에 비해 union과 conected 연산에서 필요로하는 시간이 엄청나게 줄어들었다는 것입니다. 여기서 왜 union과 connected 연산이 lg N이 되는지 설명하는 건 좀 어렵지만, 포인트는 weighted QU 연산에서는 배열의 개수가 1000배, 100000배 들어나더라도 union과 connected 연산에서는 10배, 20배 정도밖에 증가하지 않는다는 점입니다. 

---

두 번째 개선책은 경로 압축(path compression)입니다. 이는 각 노드의 연결 상태를 비교할 때, 해당 노드가 자신의 뿌리 노드를 향하게 만든 후에 연결 상태를 비교하는 방법입니다.

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

이전 노드와의 차이점이라면, root 연산의 while문에서 자신보다 상위노드의 한 단계 더 상위노드를 불러와서 연결 상태를 해결하려는 노드가 두 단계 위희 노드를 향하도록 만드는 것입니다. 이렇게 트리의 층을 줄이는 방법을 평탄화 작업이라고 합니다.