유니온-파인드 (파이썬)

현재 노드들이 같은 그룹에 속해 있는 지~

같은 그룹으로 합치고 싶을 때!

쓰는 알고리즘이다.

 

#find

1. par 배열은 각 노드의 부모를 담아놓는다.

2. par 배열의 index는 각 노드의 번호이고 그 값은 부모 노드를 의미한다.

 

처음 모든 노드의 값을 -1이라고 한다.

find 함수는 재귀적으로 자신의 부모의 부모를 탐색한다.

부모가 없는 노드를 발견하면 최상위 노드로 볼 수 있다.

최상위 노드를 찾았다면 해당 노드의 값을 리턴한다.

그 이전의 노드들은 최상위 노드의 번호로 자신의 부모 노드를 갱신한다.

 

#union

 

두 노드를 인자로 받아서 같은 그룹인지 확인하려하는 알고리즘이다.

find 함수를 통해서 해당 노드의 부모 노드를 확인한다.

위 함수에서는 인자로 받은 a,b변수에 부모의 노드의 값을 대입한다.

-> a,b는 지역변수라서 변하지 않음

 

만약 부모의 값이 같다면 같은 이미 같은 그룹이라 false를 리턴해서 함수를 종료

그렇지 않으면 다른 노드란 뜻이므로 한쪽의 부모 노드를 다른 노드의 부모로 갱신한다.

 

즉, union 함수의 목적은 두 부모 노드를 동일하게 만들어 하나의 그룹임을 확인할 수 있는 상태로 만드는 것이다.