백준알고리즘 1197 썸네일형 리스트형 크루스칼 알고리즘 (Kruskal's Algorithm) 크루스칼 알고리즘 (Kruskal's Algorithm) 크루스칼 알고리즘은 여러개의 Spanning Tree 중 최소 비용을 가지는 Tree를 구하는 알고리즘이다.주로 간선의 방향성이 없고, 모든 노드를 방문해야 하며, 간선에 가중치가 주어질 때 주로 사용된다. 이러한 최소비용을 가지는 Spanning Tree를 MST(Minimum Cost Spanning Tree), 최소비용신장트리라고 한다.MST 문제를 해결하기 위한 알고리즘으로는 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 있다. 크루스칼 알고리즘은 Merge Sort와 Union-Find를 사용하여 구현한 알고리즘이고,프림 알고리즘은 Heap을 사용하여 구현하는 알고리즘이다. 우선 Spanning Tree(신장트리)가 무엇인지 알아보자. S.. 더보기 이전 1 다음