[알고리즘]합집합 찾기(Union-find)

합집합 찾기는 대표적인 그래프 알고리즘이다. 서로소 집합 알고리즘이라고 부르기도 한다. 구체적으로는 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서 현재 이 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 이다.

예를 들어 설명해보면,

1부터 8까지의 노드가 있다

1	2	3	4	5	6	7	8
1	2	3	4	5	6	7	8

윗줄을 본인
아랫줄을 부모라고 했을때,
이 노드들은 각각이 자신을 부모로하는 집합을 가지고 있다.

만약

이렇게 연결이 되어있다면

1	2	3	4	5	6	7	8
1	1	1	4	5	6	7	8

이렇게 표현 될 것이다.

이런식으로 연결되어 있다면

1	2	3	4	5	6	7	8
1	1	2	4	5	6	7	8

이렇게 표현될 것이다.

다르게 표현하면

3은 2와 연결되어 있어서 부모인 2를 갖고 2는 1과 연결되어 있어서 1을 갖는다. 결국 3은 1과 연결되어 있는것과 마찬깆고 1의 값을 갖는다.

1	2	3	4	5	6	7	8
1	1	1	4	5	6	7	8

이렇게 recursive하게 알고리즘을 구성할 수 있다.

서로 같은 그래프에 속하는지 알아볼때는 같은 parent값을 가지고 있는지 확인하면 된다.

이제 코드로 살펴보자

#include <stdio.h>

//부모노드를 찾는 함수
int getParent(int parent[],int a){
    if(parent[a] == a) return a;
    return parent[a] = getParent(parent,parent[a]);
}
    
//각 노드의 부모를 합치는 함수
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()
{
    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,7,8);
    unionParent(parent,8,9);

    printf("1과 5는 연결되어 있나요?? %d\n",findParent(parent,1,5));
    
    unionParent(parent,1,5);
    printf("1과 5는 연결되어 있나요?? %d\n",findParent(parent,1,5));
    
    
    
    
    return 0;
}

결과: 1과 5는 연결되어 있나요?? 0
결과: 1과 5는 연결되어 있나요?? 1