[자료구조/개념] 유니온 파인드 (Union-Find)

Find 연산 

어떤 정점의 루트를 찾아주는 연산입니다.

자신이 루트라면 자신을 리턴합니다.

아래의 코드를 봅시다.

자신의 부모를 가르키는 배열이 par 이라고 정의했을 때,

자신이 루트이면 자신을 리턴하고

그렇지 않으면 재귀함수로 경로의 모든 노드의 부모를 루트로 재설정 해줍니다.

Union 연산

두 집합을 하나로 합쳐주는 연산입니다.

들어온 인자들의 루트를 찾아서 비교한 다음

루트가 다르면 둘 중 하나의 루트를 다른 하나의 루트의 자식이 되도록 변경합니다.

그렇지 않으면 (루트가 같으면) 그냥 return하여 종료시킵니다.

요약하면,

find(i) 는 i번의 루트를 찾는다는 연산이고

union(a,b) 는 a와 b를 합치겠다는 연산입니다.