합집합 찾기(Union-Find, Disjoint Set)

합집합 이란

 - 서로 중복되지 않는 부분 집합들로 나눠진 노드들에 대해 저장하고 조작하는 알고리즘이다.

 

▼표를 보면 첫 번째 행은 노드 번호이고 두 번째 행은 노드들의 관계(부모 노드)를 의미한다.

아래와 같은 형식이라 보통 배열을 사용한다.

▼노드들이 그림과 같이 연결(Union)되어있다 가정 해보자.

▼노드들이 연결되면 갱신을 할때 작은값을 기준으로 갱신한다. 

ex) 1-2-3 -> 노드3은 2, 노드 2 는 1로 바꾼다.

▲위의 그림을 보면 노드들이 1-2-3, 4-5-6 연결되어 있다.

▼각각 같은 집단에 있으므로 '재귀 함수'를 사용하여 아래 그림과 같이 나타낸다.

▼ 코드로 나타내어 보자

public class UnionFind {
    public static void main(String[] args) {
        int parent[] = new int[7];
        for(int i = 1; i < 7; i++) {
            parent[i] = i;
        }
 
        unionParent(parent, 1, 2);
        unionParent(parent, 2, 3);
        unionParent(parent, 4, 5);
        unionParent(parent, 5, 6);
        System.out.println("1과 3의 연결" + findParent(parent,1,3));
        System.out.println("4과 6의 연결" + findParent(parent,4,6));
    }
 
    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 a, int b) {
        a = getParent(parent, a);
        b = getParent(parent, b);
 
        if(a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }
 
    static int findParent(int parent[], int a, int b) {
        a = getParent(parent, a);
        b = getParent(parent, b);
        if(a == b) {
            return 1;
        } else {
            return 0;
        }
    }
}