유니온 파인드?
이론적 설명
- 유니온: 특정 2개의 노드를 연결해 1개의 집합으로 묶는 것
- 파인드: 두 노드가 같은 집합인지를 확인
코드적 설명
- 유니온: 각 노드가 속한 집합을 1개로 합침
- 파인드: 해당 집합을 대표 노드를 반환
구현방법
1) 1차원 리스트로 각 노드를 표현(연결X인 상태)
연결이 안되어 있는 상태이기에 각 노드는 그룹을 형성하지 않음
-> 자기자신이 대표 노드임
2) find 후, union수행
- 합치려는 노드들을 find로 대표 노드 찾는다.
-> find(1)=1, find(4)=4
-> find 수행시 재귀를 통해 최상단의 부모를 찾는다.(대표값과 노드가 같을 때까지)
- find는 경로 압축의 효과가 있다.(한번만 이동하면 바로 대표값을 찾음)
- 찾은 대표노드 중 작은값으로 union한다.
-> 1로 union을 진행한다.
Hi