최소 신장 트리 (MST, Minimum Spanning Tree) 그래프 내의 모든 정점을 포함하면서 사용된 간선들의 가중치 합이 최소가 되는 트리  MST 특징1) 간선(Edge)의 가중치 합이 최소2) N개의 정점을 가지는 그래프에서 반드시 (N - 1) 개의 간선만을 사용해야 함 (= 트리의 성질)3) Cycle을 포함하면 안된다  크루스칼(Kruskal) 알고리즘 - 최소 신장 트리(MST)를 구하는 알고리즘 중 하나- 매 순간 최소 가중치를 가지는 간선을 선택하여 연결하므로, 탐욕 알고리즘으로도 분류됨- 이때 Union-Find 알고리즘과 함께 사용하여 Cycle 형성되지 않을 경우 노드를 연결한다- 시간복잡도 : O(ElogE) - 실제 로직보다 간선 정보 정렬시 비용이 가장 큰 걸로 알려져..

문제 링크 https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net 문제 풀이 최소 가중치를 가지는 MST는 구했는데, 두번째 값을 구하지 못해 3시간을 소비했다. 찾아본 결과 트리의 지름을 구하는 방법을 몰랐고, 문제 지문을 제대로 읽지 못해 MST 트리 정보를 활용하는 것을 파악하지 못했다..(반성) 문제 지문을 다시 보면 아래와 같다 마음이 괘씸한 혜유는 돈을 최대한 적게 쓰면서 퀘스트를 달성하려고 한다. 혜유를 도와서 (1)모든 마을과 마을을 ..