Union-Find Algorithm, Quick-Union

Union-Find Algorithm, Quick-Find

Union-Find 알고리즘을 잘 모른다면 이 포스트 먼저 보고 옵시다!

 

1. 서론

Quick-Union 알고리즘은 Lazy Approach라는 별명이 있습니다.

 

한 마디로 이 알고리즘을 정리하면

 

"귀찮은데 나중에 해야징 ㅎ" 입니다,,

Quick-Union

처음에는 빠르지만 가면갈 수록 할 일이 늘어나는 알고리즘입니다.

 

왜 그런지 함께 알아봅시다.

 

 

2. Quick-Union 알고리즘

그림 [2-1]

또 보는 반가운 친구

 

그림 [2-1]와 같은 id Array가 있다고 해봅시다.

 

저번 시간 배운 find와 union처럼 두 노드를 연결해주는데요

 

여기서 나의 위치를 주는 것이 아니라 서로의 부모, 정확히는 루트 노드를 서로 연결해줍니다.

 

그림 [2-2]

그림 [2-2]와 같이 설정된 노드를 들여다보면

 

0,1,6,7,8,9 루트 노드가 6개 있음을 확인할 수 있습니다 (i == id[i] -> Root Node)

 

2->9

3->4->9

5->6

 

unite된 노드를 들여다보면 다음 그림과 같은 형태인 것을 확인할 수 있습니다.

그림 [2-3]

이 상황에서

 

unite(3,5)를 실행하면 어떻게 될까요?

 

서로의 루트 노드를 찾아서 unite 시켜줍니다

3의 루트노드인 9가

5의 루트노드인 6 밑으로 포함이 될것입니다.

 

find (2,3)을 실행하면 어떻게 될까요?

2의 루트노드인 9와

3의 루트노드인 9가 같기에 true를 반환할 것입니다. 

 

여기서 이상한 점을 발견합니다.

find를 통해 연결을 확인해도 root 노드를 둘 다 확인해야 하고

unite를 실행 할 때도 root노드를 둘 다 확인해야 합니다.

 

만약 최악의 경우에는 트리가 계속 깊어져서 N만큼 들어가 root를 찾아야 하죠

따라서 find와 union의 시간복잡도는 O(N)이 됩니다.

 

3. 코드

public class QuickFind {
    private  int[] id;

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

    public boolean find(int p, int q) {
        return id[p] == id[q];
    }

    public void unite(int p, int q) {
        int pid = id[p];
        for (int i = 0; i < id.length; i++)
            if (id[i] == pid)
                id[i] = id[q];
    }
}

public class Main {
    public static void main(String[] args) {
        int N = 10;

        QuickFind quickFind = new QuickFind(N);

        boolean  isConnected = quickFind.find(1, 2);
        System.out.println("Is Connected " + isConnected);

        quickFind.unite(1, 2);
        isConnected = quickFind.find(1, 2);
        System.out.println("Is Connected " + isConnected);
    }
}

4. 결론

1. Quick-Union은 트리의 깊이가 깊어질 수록 오래걸리는 알고리즘이다

(게으른 자의 최후)

2. 시간복잡도는 find, union 둘다 worst case에서 O(N)이다.