[알고리즘] Union-Find란?

오늘은 Union-Find에 대해서 알아보겠습니다.

 

---

Union-Find란?

서로소 집합을 위한 트리 연산의 단어인 Union과 Find를 합친 말입니다.

 

Union은 합집합 연산을 의미하고, Find는 주어진 원소가 어느 집합에 속해있는 지를 계산하는 역할을 합니다.

 

Union

그럼 우리는 이제 Union부터 확인해봅시다.

 

Union은 두 트리를 하나의 트리로 만드는 것을 의미합니다. 이 때 우리는 rank라는 개념으로 Union을 진행합니다.

(rank는 간단하게, 트리의 높이라고 생각해도 무방합니다.)

 

rank가 큰 트리 아래에 rank가 작은 트리를 붙여넣는 과정인데, 그림으로 확인해봅시다.

 

우리는 루트가 6과 4인 트리를 하나로 합치고 싶어합니다.

루트가 6인 트리는 rank가 3이고, 루트가 4인 트리는 rank가 2입니다. 따라서 우리는 루트 6의 트리 아래에 루트 4 트리를 합치기로 합니다.

 

아래와 같은 모양을 가졌겠네요.

하나의 트리가 됐죠?? 이러한 방식으로 우리는 Union을 진행합니다.

 

그렇다면 만약 두 개의 트리의 rank가 같게 된다면 어떻게 될까요??

어쩔 수 없이, 두 개의 트리 중 임의의 하나의 트리를 기준으로 합치게 되고 이 때는 rank가 기존보다 1 늘어나게 됩니다.

 

하지만, rank가 동일하지 않은 경우에는 Union을 수행해도 rank가 변하지 않습니다.

 

 

Find

Find는 어떤 노드에 대해서 해당 노드가 속한 트리의 루트가 무엇인지를 찾는 연산을 의미합니다.

 

재귀를 통해서 자신의 최상위 노드를 찾아가는 방법입니다. 

그림을 통해서 확인합시다.

위처럼 주어진 그래프를 배열로 표현하면 그림의 아래처럼 나타낼 수 있습니다.

그래프를 배열로 나타내는 이러한 방법은 자주 쓰일테니 알아두시면 좋습니다.

 

각 배열의 인덱스는 노드의 번호를 의미하고, 배열 내의 값은 자신의 부모 노드를 가리킵니다.

 

단, 루트노드는 부모 노드가 없으므로 자기 자신을 가리킵니다.

 

 

만약 우리가 5번 노드에 대한 최상위 노드를 알고싶다면 아래와 같은 과정을 거칩니다.

 

1. 배열에서 자신의 인덱스에 있는 값에 해당하는 배열의 인덱스에 접근합니다. 

   - 5번 노드의 값은 4이므로 배열에서 4번 인덱스에 접근합니다.

 

2. 4번 인덱스에 적혀있는 값을 확인합니다. 3이네요. 그러면 인덱스 3에 접근합니다.

 

3. 배열에서 3의 위치에 해당하는 값을 확인합니다. 똑같이 3이겠네요. 그럼 여기서 3번 노드가 최상위 노드임을 인지합니다. 따라서, 5번 노드에 해당하는 최상위 노드는 3이 되겠죠.

 

 

이러한 방식으로 각 노드에서 최상위 노드를 찾아갈 수 있습니다. 우리는 이러한 방식으로 Find를 구현합니다.

 

하지만 이렇게 자신의 최상위 노드를 매번 찾는다는 것은 시간을 많이 소모합니다. 만약 이러한 노드가 1억개가 있고, 가장 하단의 리프노드를 계속해서 find한다면 연산량이 어마어마하죠.

 

 

그래서 우리는 find를 진행할 때, 경로 압축을 진행합니다.

만약 우리가 5번 노드에 대해서 최상위 노드가 3임을 알았으면, 3의 바로 밑의 자식 노드로 5를 달아주는 것이죠.

 

이렇게 경로압축을 진행하게 되면 트리는 아래와 같이 바뀌게 될 것입니다.

 

 

find 연산을 여러번 수행하면 결국 이 트리의 rank는 2가 될 것이고, find를 굉장히 빠르게 찾아낼 수 있을 것입니다.

 

 

Union-Find의 구현

자, 이제 Union-Find를 코드로 구현해봅시다.

public class UnionFind {
    protected int[] p;
    protected int[] rank;

    public UnionFind(int N){
        p = new int[N];
        rank = new int[N];
        for(int i=0; i<N; i++){
            p[i] = i;
            rank[i] = 0;
        }
    }

    protected int find(int i){
        if(i!=p[i]) p[i] = find(p[i]);
        return p[i];
    }

    public boolean isConnected(int i, int j) {
        return find(i) == find(j);
    }

    public void union(int i, int j){
        int iroot = find(i);
        int jroot = find(j);
        if(iroot == jroot) return;

        if(rank[iroot] > rank[jroot]) p[jroot] = iroot;
        else if(rank[iroot] < rank[jroot]) p[iroot] = jroot;
        else{
            p[jroot] = iroot;
            rank[iroot]++;
        }
    }
}

find는 재귀로 구현한 것을 알 수 있고, union 메서드는 각 노드의 최상위 노드를 비교하여 다를 때, rank를 기준으로 합치는 과정임을 확인할 수 있습니다.

 

 

추가로 isConnected 메서드가 구현되어 있는데, 이는 파라미터로 받은 두 노드가 같은 트리에 속하는지를 확인하는 메서드입니다.

 

---

자, 이제 우리는 Union-Find를 알았습니다. 이제 다음 글에서는 이 Union-Find를 이용한 Kruskal 알고리즘에 대해서 다뤄봅시다.