Union find(합집합 찾기, 서로소 집합) 알고리즘

Union find 알고리즘은 여러개의 공통점이 없는 노드들이 존재할 때, 그 중 선택한 두개의 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

노드 번호	1	2	3	4	5	6	7
부모 노드 번호	1	2	3	4	5	6	7

현재는 각 노드들이 부모 노드번호로 자기 자신을 가지고 있는, 각자 자기 자신만을 집합으로 가지고 있는 상태이다. 부모 노드 번호는 자신이 어떤 부모에 포함되어 있는지를 나타낸다.

노드 번호	1	2	3	4	5	6	7
부모 노드 번호	1	2	3	3	5	6	7

만약 노드 3, 4가 연결되었다면 둘 중 더 작은 값(여기서는 1)로 부모 노드를 합친다. 이것을 합침(Union)이라고 한다.

만약 4, 5도 연결되었다면 테이블은 아래와 같을 것이다.

노드 번호	1	2	3	4	5	6	7
부모 노드 번호	1	2	3	3	4	6	7

그런데 현재의 상태에서는 3과 5가 연결되었는지를 판단하기는 쉽지 않다. 둘의 부모 노드가 3, 4로 다르기 때문이다.
이럴때는 재귀함수를 이용해서 5의 부모 노드 4를 찾은 뒤, 4의 부모 노드를 확인한다. 4의 부모 노드가 3이므로 5의 부모 노드도 3이라는 것을 알 수 있다.

따라서 합침(Union)이 완료된 결과는 다음과 같다.

노드 번호	1	2	3	4	5	6	7
부모 노드 번호	1	2	3	3	3	6	7

3, 4, 5의 부모 노드가 전부 3이므로 3개의 노드는 같은 그래프임을 알 수 있다. 
두 노드의 부모 노드를 비교해서 현재 같은 집합에 속하는지 확인하는 알고리즘을 Find 알고리즘이라고 한다.
이것이 Union - Find(합집합 찾기) 알고리즘의 전부다.

---

package com.company;

public class UnionFind {
    static int getParent(int[] parent, int x) {
        if(parent[x] == x) return x;

        return parent[x] = getParent(parent, parent[x]);
    }

    //두 노드의 부모를 합친다.
    static void unionParent(int[] parent, int x, int y){
        x = getParent(parent, x);
        y = getParent(parent, y);

        if(x>y) parent[x] = y;
        else parent[y] = x;
    }

    static int findParent(int[] parent, int x, int y){
        x = getParent(parent, x);
        y = getParent(parent, y);

        if( x == y ) return 1;  //부모 노드가 같으면(연결된 그래프이면) 1
        else return 0;
    }


    public static void main(String[] args) {
        int[] parent = new int[8];
        for (int i = 1; i < 8; i++) {
            parent[i] = i;
        }

        unionParent(parent, 1, 2);
        unionParent(parent, 2, 3);

        System.out.println(findParent(parent, 1, 3));
        //결과는 1
    }
}