유니온 파인드(Union-Find)

유니온 파인드란? 주로 그래프 이론에서 많이 사용하며 각 노드들이 어떠한 집합을 이루고 있는지를 나타내는 알고리즘 입니다.

Union 연산 : 특정 두 노드를 같은 집합으로 합치는 연산 Find연산 : 특정 노드가 어느 집합에 있는지 확인하는 연산(대표노드를 반환) 유니온 파인드의 원리 이해하기 노드가 6개가 있고 각각 자기 자신을 집합으로 하고 있습니다. Index가 노드를 나타내고 Value는 속한 집합을 나타냅니다.

Union(0, 1) Union(4, 5) Union(1, 5) 1과 5를 연결 ---> 1의 대표노드인 1과 5의 대표노드인 4를 연결한 모습 즉, 유니온 연산을 할 때는 대표 노드끼리 연결합니다. 그럼 이제 find연산을 통해 대표 노드를 찾는 방법을 알아 봅시다.

대표 노드를 찾는 방법(Find 연산) 현재 노드(인덱스 값)과 리스트의 값(집합)이 같은지 확인합니다. 다르다면 리스트의 값이 가리키는 index위치로 이동합니다 위 과정을 이동 위치의 index값...