input output 3 3 1 2 1 2 3 2 1 3 3 3 해당 문제는 최소 비용 신장 트리(MST)를 사용하는 알고리즘 중에서 Kruskal 알고리즘과 Prim알고리즘으로 해결 가능하다. 필자는 Kruskal 알고리즘을 사용하였다. Kruskal 알고리즘은 그리디 알고리즘이다. 그리디 알고리즘은 매 선택의 순간 마다 가장 최선의 선택을 하여 최종적인 해답에 도달하는 방법이다. 최선이라고 선택하였던 지역적인 해답들을 모아서 최종적인 해답에 도달했다고 해도, 그 해답이 전역적으로 최선이라는 보장은 없다. 하지만 Kruskal 알고리즘은 최선의 해답을 주는 것으로 증명되었다. Kruskal 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건에 근거하..