알고리즘 :: Union Find(Disjoint-Set) 알고리즘, 합 집합 찾기 알고리즘 (C/C++ /JAVA 구현)

Union Find 알고리즘

Union Find 알고리즘은 다른말로

Disjoint-Set(서로소 집합)알고리즘 이라고 하기도 한다.

 

다수의 노드들 중에 연결된 노드를 찾거나

노드들을 합칠때 사용하는 알고리즘이다.

 

 

1부터 10까지 노드들이 존재한다.

노드들은 서로 연결이 되어 있는데,

크게 3집단으로 나눠져있다.

1-2-3-4

5-6-7-8

9-10

 

초기 노드들간에 연결이 되기 전...

윗칸은 노드 번호

아랫칸은 부모 노드를 뜻한다.

(위와 같은 형태 때문에, Union Find를 구현할때 보통 배열을 이용한다.)

 

연결정보를 갱신한다.

갱신을 할때 작은값을 기준으로 갱신한다.

예를들어, 1과 2가 연결이 되어있으면,

'노드 2'의 값을 1로 바꾼다.

 

1-2-3-4는 모두 연결이 되어 있어,

같은 집단에 속한다.

하지만, '노드 3'과 '노드 4'의 값은 1이 아니다.

 

'노드 3'은 '노드 2'와 연결이 되어 있다.

'노드 2'는 '노드 1'과 연결이 되어 있다.

따라서 '노드 3'은 '노드 1' 과 연결되어 있다.

그래서 '노드 3'의 값의 부모노드를 1로 바꾼다.

(위 문제를 재귀방법을 통해 해결한다.)

 

재귀방법을 통해 부모노드를 갱신한다.

 

 

코드 구현

#include <stdio.h>

// 부모 노드 찾아주는 함수 
int getParent(int parent[], int x){
    if(parent[x] == x){
        // 최종 부모노드 
        return x;
    }
    return parent[x] = getParent(parent, parent[x]);
}

// 두 부모 노드를 합치는 함수 
int unionParent(int parent[], int a, int b){
    a = getParent(parent, a);
    b = getParent(parent, b);
    
    // 작은값을 부모노드로 선택 
    if(a<b){
        parent[b] = a;
        return a;
    }else{
        parent[a] = b;
        return b;
    }
}

// 같은 부모를 가지는지 확인
int findParent(int parent[], int a, int b){
    a=getParent(parent, a);
    b=getParent(parent, b);
    if(a == b){
        return 1;
    }
    return 0;
} 

int main(void){
    int parent[11];
    for(int i=1; i<=10; i++){
        parent[i] = i;
    }
    unionParent(parent, 1, 2);
    unionParent(parent, 2, 3);
    unionParent(parent, 3, 4);
    unionParent(parent, 5, 6);
    unionParent(parent, 6, 7);
    unionParent(parent, 7, 8);
    unionParent(parent, 9, 10);
    
    // 결과 확인 
    for(int i=1; i<=10; i++){
        printf("node : %d / parent : %d\n", i, parent[i]);
    }
    
    printf("1과 5는 연결이 되어있나? : %d\n", findParent(parent, 1, 5));
    printf("1과 3은  연결이 되어있나? : %d\n", findParent(parent, 1, 3));
    printf("5과 10은 연결이 되어있나? : %d\n", findParent(parent, 5, 10));
    
    return 0;
}
​

 

 

 

Java 구현

package algorithm.greedy;

public class UnionFind {

    private static int n;
    private static int[] parents;

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

    public static void unionParent(int[] parents, int x, int y) {
        x = getParent(parents, x);
        y = getParent(parents, y);

        // 더 작은 값으로 부모 노드 설정
        if (x < y) {
            parents[y] = x;
        } else {
            parents[x] = y;
        }
    }

    public static boolean isSameParent(int[] parents, int x, int y) {
        boolean result = false;
        if (parents[x] == parents[y])
            result = true;
        return result;
    }

    public static void main(String[] args) {
        n = 10;
        parents = new int[n + 1];
        // 값 초기화 및 노드 연결 전
        System.out.println("< 연결 전 >");
        for (int i = 1; i <= n; i++) {
            parents[i] = i;
            System.out.print(parents[i] + " ");
        }
        System.out.println();

        // 노드 연결
        unionParent(parents, 1, 2);
        unionParent(parents, 2, 3);
        unionParent(parents, 3, 4);
        unionParent(parents, 5, 6);
        unionParent(parents, 6, 7);
        unionParent(parents, 7, 8);
        unionParent(parents, 9, 10);    

        // 연결 후
        System.out.println("< 연결 후 >");
        for (int i = 1; i <= n; i++) {
            System.out.print(parents[i] + " ");
        }
        System.out.println();

    }
}​