728x90
반응형
유니온 파인드 Union Find
아래 두 개의 연산으로 구성된 알고리즘
- 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산
- 두 노드가 같은 집합에 속해 있는지 확인하는 find 연산
- Union 연산
각 노드가 속한 집합을 1개로 합치는 연산
ex) a∈A, b∈B일 때, union(a, b) = A∪B
- Find 연산
특정 노드 a에 관해 a가 속한 집합의 노드를 반환하는 연산
ex) a∈A 일 때 find(a)는 A집합의 대표 노드 반환
1. 대상 노드 리스트에 index값과 value값이 동일한지 확인
2. 동일하지 않으면 value값이 가리키는 index 위치로 이동
3. 이동 위치의 index값과 value값이 같을 때까지 1~2 반복 (재귀함수로 구현)
4. 대표 노드에 도달하면 재귀함수를 빠져나와 거친 모든 노드값을 대표노드 값으로 변경
반응형
