[4주차] 유니온 파인드 (Union-Find)

4번 노드 선 끊어진건 다들 모른척 해주자 솔직히

 

 

4주차에서 다뤄야 할 내용 중 최소 스패닝 트리가 있는데, 최소 스패닝 트리를 위해서는 크루스칼 알고리즘을, 크루스칼 알고리즘을 알기 위해서는 유니온 파인드를 알아야 한다.

 

그래서 유니온 파인드를 먼저 포스팅해보려고 한다.

 

---

유니온 파인드 (Union-Find)

유니온 파인드는 분리 집합(Disjoint Set) 또는 서로소 집합(Disjoint Set Union; DSU) 및 Union-Find 자료구조라고 한다.

그렇다면 이 유니온 파인드라는 녀석은 무엇일까?

 

실생활에서의 예시를 들어보자.

실생활 맞음 아무튼 ㅇㅇ...

 

탄지로, 젠이츠, 네즈코, 이노스케 네 사람은 처음에는 모르는 사이다. (그렇다고 치자고)

그런데 탄지로가 모험을 하면서 친구들을 만들게 된다.

 

탄지로는 네즈코, 젠이츠, 이노스케와 친구 관계를 맺게 되었고, 직접적으로 연결은 되어있지 않지만 네즈코와 이노스케는 자동으로 친구 관계를 맺게 된다. 

 

위와 같은 예시에서는 적은 수의 노드들이 등장하지만, 만약에 노드의 개수가 무한성처럼 많아진다면 관계를 어떻게 파악할 수 있을까?

한 번에 질의에 대해서는 DFS나 BFS 같은, 모든 노드를 탐색하는 맹목적 그래프 탐색이 가능할 것이다.

하지만 질의가 늘어나고, 그래프의 노드 연결 정보에 갱신이 발생한다면? 맹목적 탐색으로는 쓸데없이 많은 연산을 진행하게 된다.

 

따라서 유니온 파인드는

두 정점의 부모가 같으면 두 요소가 연결되어 있다.
(e. g. 탄지로와 네즈코가 친구, 젠이츠가 네즈코와 친구라면 젠이츠는 탄지로와 친구)

 

위와 같은 전제를 가지고 여러 개의 그룹이 있고, 그룹끼리는 겹치지 않는 상태에서 임의의 데이터가 같은 그룹인지 빠르게 알아내거나 두 그룹을 합치는 작업을 빠르게 진행하기 위해 사용하는, 그리고 그것을 '트리'의 형태로 나타내는 일종의 자료구조다.

 

유니온과 파인드

유니온 파인드는 원어로 보면 Union-Find다. Union Find가 아니다. 이처럼 '유니온'과 '파인드'는 별개의 연산이며

유니온보다 파인드가 선행된다.

 

파인드 (Find)

파인드는 재귀적으로 해당 노드의 부모를 계속 찾아 최종적으로 해당 노드의 루트가 무엇인지를 알 수 있도록 하는 연산이다.

 

 

유니온 (Union)

유니온은 두 개의 서로 다른 노드의 부모가 같다면 두 노드를 합치는 연산이다.

 

 

 

위 과정을 계속 반복하며 결론적으로는 모든 노드의 부모 노드를 루트 노드인 1으로 만들어주는 것, 그리고 이 노드들이 같은 루트 노드를 갖는, 같은 그룹임을 알 수 있도록 만들어 주는 것을 유니온 파인드라고 한다.

 

이렇게 각 노드간의 연결 관계를 찾고 그룹을 묶는 유니온 파인드는 단독적으로 사용되기 보다는 크루스칼 알고리즘에서 활용해 최소 스패닝 트리를 찾는 등의 활용으로 이어진다.

 

출처

유니온 파인드 (다빈치코딩 / 위키독스) : https://wikidocs.net/206632

분리집합 (Disjoint set) : Union-Find (4legs Archives 티스토리 블로그) : https://4legs-study.tistory.com/94?category=886581

Chat GPT