📚 Reference
📜 Chapter
‣
MST (Minimum Spanning Tree)
Union-Find (유니온 파인드)
- Union-Find
- 유니온 파인드
- '합치고(Union)', '찾는(Find)' 알고리즘이다.
- 여러 개의 노드가 있을 때, "어떤 두 노드가 같은 그룹에 속해 있는가?"를 아주 빠르게 판별하기 위해 사용한다.
- 보통 '서로소 집합(Disjoint Set)' 알고리즘이라고도 부른다.
핵심 기능 2가지
- 핵심은 각 그룹의 '대표(루트 노드)'를 정하는 것이다.
- Find: 특정 노드가 어느 그룹에 속해 있는지 찾는 연산이다. (보통 그 그룹의 루트 노드를 반환한다.)
- Union: 서로 다른 두 그룹을 하나로 합치는 연산이다. (한쪽의 루트를 다른 쪽의 루트로 연결한다.)
JavaScript 코드로 이해하기
- 배열 하나만 있으면 된다.
- 배열의 각 인덱스는 노드 번호이고, 값은 부모 노드 번호를 의미한다.