Union Find :: 합집합 찾기 :안경잡이개발자 리뷰

Union Find( 유니온 파인드) 는 대표적인 알고리즘입니다. 바로 합집합 찾기라는 의미를 가진 알고리즘인데, 서로소 집합(Disjoint-set) 알고리즘이라고 부릅니다. 구체적으로 여러 개의 노드가 존재할때,  두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

위와 같이 여러 개의 노드가 서로 자유분방하게 존재한다고 생각해보자. 이와 같이 모두 연결되지 않고 가가 자기 자신만을 집합의 원소를 가지고 있을때를 다음과 같이 표현할 수 있다. 모든 값이 자기 자신을 가르키도록 만드는 것이다. 아래 표에서 첫번째 행은 '노드 번호'를 의미하고, 두번째 행은 '부모 노드 번호'를 의미합니다. 즉,  자신이 어떠한 부모에 포함되어있는지를 의미합니다.

 

이 떄 위와 같이 1과 2가 연결되었다고 해봅시다. 이러한 '연결성' 우리가 프로그래밍 언어로 어떻게 표현할 수 있는지에 대한 내용을 바로 union-find 라고 생각하시면 이해가 쉽습니다.

 

바로 위와 같이 표현합니다. 2번째  인덱스의 값이 '1'이 들어가는 겁니다. 이렇게 부모를 합칠때는 일반적으로 더 작은 값 쪽으로 합칩니다. 이것을 바로 합침(Union) 이라고 합니다.

 

그렇다면 위와 같이 2와 3도 연결되었다면 어떻게 표현할까요?

위와 같이 표현됩니다. 다만, 여기서 한 가지 의아한 점을 발견됩니다.  바로 '1과 3이 연결되었는지를 어떻게  파악?'입니다. 1과 3은 부노가 각각 1과 2로 다르기 때문에 '부모 노드'만 보고는 한 번에 파악할 수 없습니다. 그래서 재귀함수가 이용됩니다.

 

  3의 부모를 찾기 위해서는 먼저 3이 가리키고 있는 2를 찾는 겁니다. 그러면 2의 부모가 1을 가리키고 있으므로 그제서야 '결과적으로 3의 부모는 1이 되는 구나!'하고 파악할 수 있습니다. 이러한 과정은 재귀적으로 수행될 때 가장 효과적이고 직관적으로 언어를 작성할 수 있습니다. 그래서 결과적으로 합침(Union) 연산이 다 수행되고 나면 다음과 같이 표가 구성됩니다.

 

노드 1,2,3 의 부모가 모두 1이기 때문에 이 세가지 노드는 모두 같은 그래프에 속한다고 할 수 있다.

find 알고리즘은 두 개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는 알고리즘입니다.

#include <stdio.h>

int getParent(int parent[], int x){
 
 if(parent[x] ==x)
 	return x;
 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;
    else 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);
	printf("1과 5는 연결되어있나요? %d\n", findParent(parent, 1, 5));
	unionParent(parent, 1, 5);
	printf("1과 5는 연결되어있나요? %d\n", findParent(parent, 1, 5));



}