[JS] 섬 연결하기: 크루스칼 알고리즘과 union-find.

새로운 알고리즘이네요.그리디(Greedy) 알고리즘의 일종인 크루스칼(Kruskal) 알고리즘 입니다. 크루스칼 알고리즘 목적: 최소 신장 트리 구하기 주요 기능: Union - Find를 통한 최소 비용외의 간선 삭제 이런 노드들이 있다고 가정하면, 간선 [3 - 4]를 제외한 경로가 비용이 최소가 되는 경로입니다. 이런 경로를 구하는 방법은 다음과 같습니다. 1. 비용의 순서대로 정렬. 2. 해당 노드의 부모를 갱신. 3. 비용 계산으로 진행됩니다. union - find 연산은 node의 부모가 다를때 각 노드의 부모를 갱신해주는 알고리즘입니다. 부모가 같다면 해당 간선으로 사이클이 발생할 수 있기 때문에 부모가 같은 경우는 제외하게 됩니다. 종종 union 연산 시 갱신하는 parent가 최상단의..

2022.09.17