Union-Find Algorithm, Quick-Find

 

1. 정의

* Union Command, 두 오브젝트를 연결하는 것

* find query, 두 오브젝트가 연결되어있는지 확인하는 것

Union

2. 용도

그림과 같이 A 노드와 B 노드가 있다고 해봅시다.

 

A와 B가 연결되어 있는지 확인하고 싶을 때

 

find query를 사용합니다.

 

중간 노드들 간에 연결을 union command를 사용합니다.

 

Union-find를 통해 객체간에 연결 혹은 집합 곧 포함관계를 알 수 있습니다.

 

예를 들어 컴퓨터간 네트워크 연결 확인 등 있습니다.

 

3. Quick-Find 알고리즘

 

말 그대로 find가 빠른 대신 union이 느린 Algorithm입니다.

그림[3-1]

다음 그림 [3-1] 같은 id라는 Array가 있다고 합시다.

 

Quick-find 알고리즘에서 find는

 

id[1] 와 id[2] 의 값이 같은지 확인합니다.

 

그림 [3-1]은 하나도 같은 값이 없기 때문에 독립된 집합들임을 알 수 있습니다.

 

이렇게 단순 값을 비교하기 때문에 find가 굉장히 빠릅니다.

 

따라서 O(1)의 시간복잡도를 가집니다.

 

그림 [3-2]

그림 [3-1] 에서 unite(2,3)을 실행할 경우 id[2]의 값이 id[3]의 값으로 Assign되는 것을

 

그림 [3-2] 와 같이 확인할 수 있습니다.

 

또한 id[2]와 id[3]은 같은 값을 가지기 때문에

 

find(2,3)에 true를 반환할 것입니다.

 

하지만 Union에서 오래 걸리는데요 왜냐 만약 3의 값을 가진 노드를 모두 확인해봐야하기 때문입니다.

 

Union 과정에서 모든 배열을 순회해야 하기 때문에 O(N)의 시간복잡도를 가지게됩니다.

 

그림 [3-3]

 

unite(2,3) 을 실행할 경우 2의 값을 다 가진 노드들을 다 3으로 바꾸어줘야 합니다.

 

꼭 바꿔주는 것 뿐만아니라 값들을 확인해야 하기 때문에 무조건 N번 순회를 해야 합니다.

 

4. 코드 (JAVA)

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);
    }
}

 

5. 결론

 

find -> O(1)

unite -> O(N)