📌 유니온파인드란?
- 유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.
- 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다.
노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어진다. - 트리 구조로 이루어진 자료구조 중 한가지로 생각되기도 한다.
✅ 동작과정
-
8개의 단절된 노드들이 있다.
이 노드들은 배열에 자기 자신의 값을 가지고 있다.
-
이 중에 1 2 노드를 연결하고 4 5 6 노드들을 연결하고 싶다.
-
우선 1 2 노드를 합쳐보자
합치는 방법은 간단하다 2번 노드의 배열 값을 1번 노드의 배열 값으로 바꿔주면 된다.
-
4 5 6도 마찬가지로 바꿔보자
4와 5를 연결하고 5와 6을 연결하면 그림처럼 배열이 바뀐다.
-
각각 노드의 루트 노드를 비교해서 서로 다르다면 두 노드는 연결되어 있지 않은 것이다.예를들어 2번과 6번 노드가 연결되어 있는지 확인하고 싶다면
2번 노드의 부모를 찾는 과정
배열의 2번에 있는 값을 확인한다. 1번이다.
배열의 1번에 있는 값을 확인한다. 1번이다.
배열의 인덱스와 값이 일치한다.
그렇다면 1번 노드가 2번 노드가 속해있는 트리의 루트 노드이다.
하지만 이렇게만 바꾸면 문제가 생긴다. 트리의 문제 중 하나인 한쪽으로만 자식이 몰려있는 편중현상이 생길 수 있는 것이다.
Find연산에서 재귀를 통해 루트 노드를 찾아야하는데 이렇게 편중되어 있으면 탐색하는데 시간이 많이 걸린다.
위의 편중 문제를 해결하기 위해 합치는 Union연산을 할 때
루트 노드를 찾는 탐색과정을 통해 루트노드에 연결하는 과정을 거쳐
결과적으로 위의 그림처럼 트리가 형성된다.
1 2 를 연결하고 4 5 6을 연결한 유니온 파인드의 트리구조이다.
이제 1과 4번 노드를 연결하고 싶다면 위의 그림처럼 바뀔 것이다.
Reference
꿈꿈