📚 목차
요약
1. 유니온 파인드
1. 유니온 파인드
- 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지 확인하는 find연산으로 구성된 알고리즘이다.
2. 유니온 파인드의 핵심 이론
- 노드 값과 노드의 대표 노드를 나타내는 배열을 만든다. 대표 노드는 각 노드 값이 된다.
| 노드 |
1 |
2 |
3 |
4 |
5 |
6 |
| 대표 |
1 |
2 |
3 |
4 |
5 |
6 |
- 간선이 생기면 두 노드는 하나의 집합이 된다. 따라서 대표 노드를 업데이트 시킨다.
- 중요한 점은 대표 노드의 대표 노드의 대표 노드 … 의 대표 노드(최고참 노드)끼리 비교 후 최고참 노드의 대표 노드를 다른 최고참 노드로 업데이트 시키는 것
| 노드 |
1 |
2 |
3 |
4 |
5 |
6 |
| 대표 |
1 |
2 |
3 |
1 |
5 |
6 |
- 하나의 집합이되는 union 연산이 이뤄질 때마다 이를 반복한다.
| 노드 |
1 |
2 |
3 |
4 |
5 |
6 |
| 대표 |
1 |
2 |
3 |
1 |
5 |
5 |