유니온 파인드
서로서 집합(disjoint-set) 자료 구조, 또는 합집합을 만드는 연산 union과 같은 집합인지 찾는 (merge_find )로 이루어짐.
파인드(find) : 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. 재귀적인 구조로 "대표" 하는 원소를 찾고 두 원소가
같은 지를 판단함.
유니온(union) : 두 개의 집합을 합친다. ("대표" 와 "대표를 비교하여 하나의 "대표"를 저장)
기본 구조
단순 배열로 구현가능. 1~n까지 n개의 노드가 있다고 가정하면 각 노드의 값으로 저장될 배열을 하나 생성.
parent [n]
원소 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
대표값 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
union
원소들의 대푯값을 하나로 만들어줘야 함.
union(2,3)
원소 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
대표값 | 1 | 2 | 2 | 4 | 5 | 6 | 7 |
union(3,4)
원소 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
대표값 | 1 | 2 | 2 | 2 | 5 | 6 | 7 |
모든 원소를 대푯값으로 변경하는 이유는 find 연산에서 연결 리스트 구조로 되어있다면 O(n) 만큼의 시간이 소요되기 때문에
모든 원소가 하나의 대푯값을 가지도록 union 하면 O(1). (코드에서 이과정은 find에서 함)


find
해당 원소의 대표값을 찾는 함수.
union에서는 실제로 모든 원소를 탐색하지 않고 해당 원소의 대푯값만 변경되기 때문에 모든 원소를 대푯값으로 변경은 find() 연산에서 이루어짐.

최적화
union 하는 과정에서 개수가 적은 원소를 가진 집합을 큰 원소의 집합으로 한다면 최적화를 할 수 있음.
rank라는 배열을 만들어 각 대표와 연결된 개수를 저장하여 비교하여 union 하면 됨.
'알고리즘 > 알고리즘_theory' 카테고리의 다른 글
트리에서의 다이나믹 프로그래밍 (0) | 2022.04.12 |
---|---|
병합 정렬 (0) | 2021.10.10 |