[Algorithm] Union - Find (유니온 파인드)란?

• 이 글은 (https://m.blog.naver.com/ndb796/221230967614) 블로그를 보고 작성하였습니다.

Union Find

유니온 파인드는 대표적인 그래프 알고리즘입니다. 여러 개의 노드가 있을 때 두 가지의 노드 하나의 그래프로 연결되어 있는지 판별하는 알고리즘입니다.

 

먼저, 배열을 만들어서 해당 노드번호로 부모 노드번호를 가리키게 합니다. 처음에는 당연히 연결된 그래프가 없기 때문에 각자 자신의 노드번호를 가리키게 됩니다.

 

1과 2를 연결하게 되면 합친다는 뜻에서 Union이라고 부르고 노드번호 중 작은 노드번호가 부모노드가 됩니다.

 

이렇게만 구현할 경우 2와 3이 연결하게 되면 부모노드가 2가 되는데 1과 3이 같은 그래프로 연결되어 있는지는 알 수가 없습니다. 따라서 재귀함수를 사용하여 3의 부모노드는 2이고 2의 부모노드는 1이다 이런방식으로 구현을 해야합니다. Find 함수를 구현하여 부모노드가 같으면 같은 그래프라고 판별할 수 있습니다.

필수 구현함수

• getParent : 각 노드의 부모노드 구하기
• unionParent : 두 개의 노드 합치기 ( 부모 동일)
• findParent : 같은 그래프로 연결되어 있는지 확인

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.