[알고리즘] 유니온 파인드 (Union-Find) :: 늦깎이 IT

---

이 포스팅은 [이곳] 에서 수정 및 보완되었습니다. 꼭! 참고하시기 바랍니다.

이 포스팅에서는 유니온 파인드의 연산 과정을 [그림] 위주로 이해하기만 하면 될 것 같습니다.

---

오늘은 '유니온 파인드 (Union-Find)' 알고리즘을 포스팅합니다.

유니온 파인드는 대표적인 그래프 알고리즘으로써 서로소 집합(Disjoint-Set) 알고리즘이라고도 불린다.

여러 개의 노드가 존재할 때, 두 개의 노드를 선택해서 이 노드들이 서로 같은 그래프에 속하는지 판별하는

알고리즘이다.

아래와 같은 노드들이 있다고 가정한다.

 위 그림에서 노드 1, 2, 5와 3, 4, 6은 각각의 그룹으로 나뉘어있다. 위의 상태에서 5번 노드가 어느 그룹에 속해있는지 확인하는 것을 Find-Set이라고 한다.

임의의 노드들이 같은 그룹에 속해있는지 확인하기 위해서는 그 노드들의 부모노드가 같은지 확인하면 된다.

Union과정을 모두 거치면 아래와 같은 그림과 표를 만들 수 있다.

이때, 노드 1과 노드2의 부모 노드 값이 같으므로, 같은 그룹에 속해있다. 그러나 노드 3과 노드 5는 부모 노드의 값이 다르므로 다른 그룹에 속해있다는 것을 알 수 있다.

또한, 노드3과 5를 잇는 간선을 추가해주면 어떻게 될까?

이전에는 2개의 그룹으로 나뉘었지만, 3과 5가 연결됨으로써 모든 노드들이 하나의 그룹에 속하게 되었다.

이처럼 각각 다른 그룹이었던 노드들을 하나의 그룹으로 합치는 것을 Union이라고 한다.

---

[Find-Set 과정]

[의사 코드]

FIND-SET(x)
    if x != p[x]
        then p[x] ← FIND-SET(p[x])
    return p[x]

1)번 라인에서 FIND-SET 함수는 x의 부모 노드를 찾는 함수이다.

2)번 라인에서 x와 p[x]의 값이 다르다면, x의 부모 노드는 x자신이 아닌 다른 노드이므로 재귀함수를 통해 부모노드를 찾아 리턴한다.

3)번 라인에서 x의 값이 p[x]와 같다는 것은, x의 부모노드가 자기자신이라는 뜻이므로 p[x]를 리턴한다.

[JAVA 코드]

public static int findSet(int[] parent, int node) {
 
        if (parent[node] == node)
            return node;
        else
            return parent[node] = findSet(parent, parent[node]);
    }

[시간 복잡도]

 Find-Set의 시간복잡도는 트리의 높이와 같다. 위의 그림에서 [1 - 2 - 5]로 이루어진 그룹에서 Find-Set 연산을 진행하면 O(1)만큼의 시간이 걸리는데, 그 이유는 트리의 높이가 1이기 때문이다.

최악의 경우는 부모 노드가 하나의 자식만을 갖는 연결리스트 형태를 갖는 경우이다. 

N개의 노드가 일렬로 연결되어 있을 때 트리의 높이또한 N이며 이 경우 Find-Set의 시간 복잡도는 O(N)이다.

[Union 과정]

1. 초기상태에서는 각 노드들끼리 어떠한 간선으로도 연결되어 있지 않으므로 각각 독립된 그룹으로 나뉘어 있다고 본다.  그리고 각 노드들은 자신의 부모노드의 번호를 저장하지만, 초기 상태에는 자기 자신을 부모노드로 저장하는데 이 과정은 Make-Set이라고 한다.

2. 노드1과 노드2가 간선으로 연결되면, 각 노드들의 부모 노드를 변경시켜준다. 여기서는 더 작은 값의 노드가

부모노드가 된다. 1과 2가 연결되었으므로 2의 부모노드는 1로 변경시켜준다.

3. 노드 2와 노드 5를 연결시켜준다. 이때 노드2와 노드5를 비교하여 노드 5의 부모 노드값을 갱신해야한다.

우선, 노드 2와 노드 5를 비교했을 때, 5보다 2가 더 작으므로 노드 5의 부모노드를 2로 갱신한다.

하지만 노드2의 부모노드가 노드 1이므로 노드 5의 부모또한 노드1로 바꿔준다.

4. 노드3과 노드 6을 연결한다. 3이 6보다 작으므로, 노드 6의 부모노드는 3으로 바꿔준다.

5. 노드 3과 노드 4을 연결한다. 3이 4보다 작으므로, 노드 4의 부모노드는 3으로 바꿔준다.

[의사 코드]

UNION(u, v)
    x ← FIND-SET(u)
    y ← FIND-SET(v)
 
    p[x] ← y;

1)번 라인에서 UNION 함수는 노드 u와 v를 합집합하는 연산을 한다.

2)번 라인에서 각각의 노드에 대한 부모 노드를 찾는다.

5)번 라인에서 어느 한 집합의 부모노드를 다른 집합의 부모노드로 변경한다.

[JAVA 코드]

public static void union(int[] parent, int node1, int node2) {
 
        int a = findSet(parent, node1);
        int b = findSet(parent, node2);
 
        if (a != b)
            parent[a] = b;
    }

[시간 복잡도]

 UNION 함수의 시간복잡도는 O(1)의 시간이 걸린다. 단순히 X노드의 부모를  Y노드의 부모로 바꾸기만 하면된다.

물론 노드 X와 Y에 대해서 부모노드를 찾는데 걸리는 시간은 Find-Set 연산을 수행하는 시간인 O(N)이 걸린다.

---

[JAVA 테스트 코드]

public static void main(String[] args) {
 
        int[] parent = new int[7];
        for (int i = 1; i < 7; i++)
            parent[i] = i;
 
        union(parent, 1, 2);
        union(parent, 2, 5);
        union(parent, 3, 4);
        union(parent, 3, 6);
 
        if (findSet(parent, 1) == findSet(parent, 2))
            System.out.println("1과 2는 같은 집합이다.");
        else
            System.out.println("1과 2는 같은 집합이 아니다.");
 
    }