해결과정 - 크루스칼 알고리즘오랜만의 최소 스패닝 트리 알고리즘이여서 현재 알고있는 알고리즘은 크루스칼 알고리즘, 프림 알고리즘이 있는데 크루스칼 알고리즘이 구현이 간단하여 이걸로 푸는 편이다. 잠깐 이 알고리즘을 설명하면 현재 간선들중 작은 간선들만 확인하며 서로 이었을때 사이클이 생기면 간선을 추가하지 않고 사이클이 생기지 않으면 간선을 추가해 준뒤 모든 노드가 이어져 트리를 형성하면 종료 하는 알고리즘이다. 다익스트라 알고리즘하고 동일하게 증명이 가능하여 항상 최적의 루트를 보장해 주는 알고리즘이다. 이 문제의 경우 2개의 도시로 분할해야 되므로 트리를 구한뒤 그중 가장 큰 값의 간선을 제거해 주면 두개의 도시로 분할이 된다 #define _CRT_SECURE_NO_WARNINGS#include #..
