📚 Reference

📜 Chapter

‣

MST (Minimum Spanning Tree)

Union-Find (유니온 파인드)

• Union-Find
• 유니온 파인드
• '합치고(Union)', '찾는(Find)' 알고리즘이다.
• 여러 개의 노드가 있을 때, "어떤 두 노드가 같은 그룹에 속해 있는가?"를 아주 빠르게 판별하기 위해 사용한다.
• 보통 '서로소 집합(Disjoint Set)' 알고리즘이라고도 부른다.

핵심 기능 2가지

• 핵심은 각 그룹의 '대표(루트 노드)'를 정하는 것이다.
  • Find: 특정 노드가 어느 그룹에 속해 있는지 찾는 연산이다. (보통 그 그룹의 루트 노드를 반환한다.)
  • Union: 서로 다른 두 그룹을 하나로 합치는 연산이다. (한쪽의 루트를 다른 쪽의 루트로 연결한다.)

JavaScript 코드로 이해하기

• 배열 하나만 있으면 된다.
• 배열의 각 인덱스는 노드 번호이고, 값은 부모 노드 번호를 의미한다.