Union-Find(합집합 찾기)란?

Union-Find 란?

union-find 연산은 Kruskal의 알고리즘에서만 사용되는 것은 아니고 일반적으로 널리 사용된다. union(x, y) 연산은 원소 x와 y가 속해있는 집합을 입력으로 받아 2개의 집합의 합집합을 만든다. find(x)연산은 원소 x가 속해있는 집합을 반환한다. 구체적으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

 

출처 : https://m.blog.naver.com/ndb796/221230967614

 

위와 같이 여러 개의 노드가 연결되지 않은 채로 있다고 가정하자. 여기서 union(1, 4)와 union(5, 2)를 하면 아래와 같은 집합으로 변환된다.

 

{1, 4}, {5, 2}, {3}, {6}, {7}, {8}   

 

위와 같이 합쳐지는 것이다. 더 이해가 필요하기 때문에 구체적인 예시를 들어보겠다.

 

 

출처 : https://m.blog.naver.com/ndb796/221230967614

위의 연결되어 있지 않은 노드들은 각자 자기 자신만을 집합으로 갖고 있는 상황이다. 따라서 첫 번째 행은 '노드 번호' 를 의미하고, 두 번째 행은 '부모 노드 번호'를 의미한다. 따라서 자기 자신의 부모 노드를 확인 할 수 있다.

 

출처 : https://m.blog.naver.com/ndb796/221230967614

 

위와 같이 1과 2가 연결되었다고 생각해보자. 연결된 것을 코드로 표현을 하려면 union-find을 이용해서 생각하면 된다.

 

출처 : https://m.blog.naver.com/ndb796/221230967614

이렇게 2의 부모가 1이 되었다. 보통 일반적으로 노드 끼리 연결을 할 때는 노드의 번호가 작은 쪽이 부모가 된다. 

바로 이것을 합침(Union)이라고 한다. 

 

출처 : https://m.blog.naver.com/ndb796/221230967614

 

다음에는 2와 3이 연결되었다고 생각해보자. 

 

출처 : https://m.blog.naver.com/ndb796/221230967614

3의 부모가 2가 되었다. 하지만 위의 그래프는 1 - 2 - 3이 모두 연결이 되어있지만, 2의 부모는 1이고 3의 부모는 2이기 때문에 부모가 다르다. 따라서 한번에 파악할 수가 없기 때문에 여기서 재귀함수가 사용된다.

 

예를들어 3의 부모를 찾기 위해서는 현재 3의 부모인 2를 찾는 것이다. 그 다음에 2의 부모인 1을 찾아간다. 결과적으로 3의 부모는 1이 되는 것을 알 수 있다. 이러한 과정은 재귀함수를 이용하면 아주 효과적으로 코드를 구현할 수 있다. 

 

출처 : https://m.blog.naver.com/ndb796/221230967614

이렇게 노드 1, 2, 3의 부모가 모두 1이기 때문에 이 세 가지 노드는 모두 같은 그래프에 속한다고 할 수 있다. 그리고 Find 알고리즘은 두개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는 알고리즘이다. 

 

 

 

[그림 출처] + 블로그 내용[참고] 

https://m.blog.naver.com/ndb796/221230967614

17. Union-Find(합집합 찾기)

자세한 내용은 위 블로그인 "동빈나"님 블로그로 가서 보세요!