[알고리즘] 서로소 집합 자료구조

1. 서로소 집합 자료구조

• 서로소 집합: 서로 공통 요소가 없는 서로 다른 집합 = 교집합이 없는 서로 다른 집합
• 서로소 집합 자료구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
  • 서로소 집합 자료구조의 연산: 합집합 연산 union, 찾기 연산 find
  • 즉! union, find 연산을 하게 되면 두 집합 간의 공통적인 요소가 있느냐 없느냐를 판단할 수 있는 연산
  • 스택과 큐가 push, pop 연산 과정이 있는 것처럼

2. Union(합집합), Find(찾기)

• 서로소 집합 자료구조를 표시할 때는 기본적으로 트리 자료구조 이용
  • 트리 자료구조는 계층을 갖고 있다. 즉, 노드들 간의 부모-자식 관계가 있음을 가정

트리 자료구조를 활용해 집합을 표현하는 서로소 집합 계산 알고리즘

1. union연산 정보 중 1개를 확인하여 서로 연결된 두 노드 A,B를 확인
2. 두 노드 A,B 각각의 루트 노트 A',B'를 알아낸다. (이때, find연산을 수행하는 것)
3. 보통은 A',B' 중 값이 작은 노드를 부모 노드라고 가정하고 연결시킨다.
   예를 들어 A'< B'이라면, B' -> A'로 연결시킨다. (이때, union연산을 수행하는 것)
4. 나머지 union연산 정보를 순차적으로 받으면서 1~3번 과정을 반복한다.

그림 설명

참고
https://techblog-history-younghunjo1.tistory.com/257