Overview 최소 신장 트리(Minimum Spanning Tree | MST)란 한 그래프에 속해 있는 모든 정점을 잇는 최소 비용의 부분 그래프를 의미합니다. 다시 말해서, 가장 적은 비용으로 모든 정점들을 이어주는 그래프를 의미하는 것입니다. 네트워크 장비에 관한 포스팅에서 스위치(네트워크 장비)를 통해 여러 개의 컴퓨터들을 연결하는 과정에 대해서 살펴보았습니다. 이 때, 컴퓨터 사이에 두 개 이상의 네트워크 경로가 존재할 경우, 네트워크 루핑 현상이 발생할 수 있으며, 이를 막기 위해 스위치는 스패닝 트리 프로토콜을 통해 컴퓨터와 컴퓨터 사이에는 단 하나의 루트만 존재하게끔 조정해 줍니다. 이 스패닝 트리 프로토콜이 바로 최소 스패닝 트리와 밀접하게 연관되어 있습니다. 최소 신장 트리는 최소 ..

풀이 이전 포스팅에서 다루었던 최소 스패닝 트리 문제를 아주 간단하게 응용하여 풀 수 있는 문제입니다. 최소 스패닝 트리를 이전과 마찬가지로 구하고 나서, 최소 스패닝 트리를 잇는 가장 가중치가 큰 간선을 제외하면 가장 작은 비용으로 두 마을을 나누어줄 수 있습니다. 따라서 최소 스패닝 트리를 생성할 때에 추가되는 간선의 가중치 중, 가장 큰 값을 저장해두었다가 트리의 생성 비용에서 제거해주면 됩니다. 소스 코드(JAVA) import java.util.*; import java.io.*; public class Kruskal { public static int[] parent; public static ArrayList edgeList; public static void main(String[] arg..