[Algorithm] Union-Found(합집합 찾기)

Union-Found 란?

대표적인 그래프 알고리즘이다.

여러개의 노드가 존재할 때, 2개의 노드를 선택하여 선택한 2개의 노드가 같은 그래프에 속하는 지 확인하는 알고리즘이다.

원리

여러 노드들이 존재한다고 하고, 그 노드들의 수만큼 배열을 만들어준다.

각 노드의 배열의 값은 그 노드의 부모 노드의 값이다.

즉, 모든 노드들이 서로 연결되어 있지 않은 상태라면, 배열의 값은 노드의 값과 동일하다.

만약 서로 연결되어 있는 노드들이 있으면, 더 작은 노드가 부모노드이다. 연결된 노드 중 큰 노드의 값이 작은 노드로 바뀌면 2개의 노드는 서로 연결되어있는 것이다.

만약, 자식노드에게 또 자식노드가 있을 경우 재귀함수를 사용하여, 제일 root 부모노드를 찾아, 본인의 값을 root부모 노드의 값으로 바꿔준다.

구현

#include <stdio.h>

// 특정한 노드의 부모를 찾는 함수 
int getParent(int parent[], int x) {
    if(parent[x]==x) return x; // 노드의 값이 자기자신인 경우 부모노드이므로 return
    return parent[x] = getParent(parent, parent[x]);
}

// 두 노드의 부모를 합치는 함수
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;

}

// 같은 부모를 가지는지 확인(같은 그래프에 속해있는 지 확인)
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]; // 노드가 10개 있다. 

    for(int i=1;i<11;i++) {
        parent[i] = i; // 자기자신을 부모로 가리키게 함 
    }

    unionParent(parent, 1, 2); // 노드 1과 노드 2를 연결
    unionParent(parent, 2, 3); // 노드 2와 노드 3을 연결
    unionParent(parent, 3, 4); // 노드 3과 노드 4를 연결

    unionParent(parent, 5, 6); // 노드 5와 노드 6을 연결
    unionParent(parent, 6, 7); // 노드 6과 노드 7을 연결
    unionParent(parent, 7, 8); // 노드 7과 노드 8을 연결 

    // 0일 경우 다른 그래프. 1일 경우 같은 그래프 
    printf("1과 5는 연결되어 있나요? %d\n", findParent(parent, 1, 5));
    printf("1과 4는 연결되어 있나요? %d\n", findParent(parent, 1, 4));

    return 0;
}

reference: https://www.youtube.com/watch?v=AMByrd53PHM&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=18