1. 서로소 집합 알고리즘
1.1. ‘서로소 집합(Disjoint Sets)란
-
공통 원소가 없는 두 집합을 의미함

1.2. 서로소 집합 자료구조(= 합치기 찾기 자료구조)
- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조임
- 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불림
<aside>
📌 서로소 집합 자료구조의 연산 (2 종류)
- 합집합(Union)
- 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산임
- 찾기(Find)
- 특정한 원소가 속한 집단이 어떤 집합인지 알려주는 연산
</aside>
1.3. 서로소 집합 자료구소 동작 과정
- 여러 개의 합치기 연산이 주어졌을 때, 서로소 집합 자료구조의 동작 과정
-
각각의 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인함
-
A와 B의 루트 노드 A’, B’를 각각 찾음
-
A’를 B’의 부모 노드로 설정
-
모든 합집합(Union) 연산을 처리할 때까지 1번의 과정을 반복함
1) 초기 단계: 노드의 개수 크기의 부모 테이블을 초기화
- 처음에는 부모를 자기 자신으로 설정함
- 각각의 집합은 서로 다른 집합이며 원소가 1개씩 존재함

2) 1단계: 각 루트 노드를 먼저 찾고, 부모 노드 설정하기
- 예: Union(1, 4)
노드 1과 노드 4의 루트 노드를 각각 찾음
- 현재 루트 노드는 각각
1과 4이므로,
더 큰 번호에 해당하는 루트 노드 4의 부모를 1로 설정
- 일반적으로 합치기 연산 수행에는 더 큰 루트노드가 더 작은 루트 노드를 가리키도록 해서 테이블을 갱신함

3) 2단계: 1단계 수행을 반복