최소 신장 트리

문제 링크 : https://www.acmicpc.net/problem/17472 문제 설명이 아주 자세하게 나와있다.일반적인 하나의 알고리즘을 이용하는 게 아닌 여러 알고리즘을 사용하여 해결할 수 있는 문제이다.우선 문제에서 구하고자 하는것을 보면 결국 모든 섬이 하나의 집합으로 만들어져야 하는데이때 최단거리를 구하는 문제이다. 얼핏 봤을 때 최소 신장 트리(MST) 알고리즘을 사용하면 될 것처럼 보인다.일반적인 MST알고리즘 문제는 간선과 정점을 직접 제공하는경우가 많다.하지만 이 문제에서는 아무것도 주어져있지 않다. 문제에서 주어진 그림을 자세히 보면 힌트를 주듯 각 섬을 하나의 번호로 묶은 것을 볼 수 있다.따라서 문제를 해결하는 과정은 아래와 같다.1. 섬을 정점이라고 생각하고 맞닿아 있는 점끼..

문제 링크 : https://www.acmicpc.net/problem/1197 이 문제는 최소 신장 트리(Minimum Spanning Tree, MST) 알고리즘 구현 문제이다.MST 알고리즘은 모든 노드들을 연결했을 때 가장 적은 비용의 간선 집합을 찾는 알고리즘이다.간단한 MST에 대한 설명은 아래와 같다.  위와 같은 그래프가 있다고 가정한다.정점 사이에는 가중치가 있는 간선이 있다.MST 알고리즘은 해당 그래프의 모든 정점들을 잇는 가장 최소비용의 간선 집합을 찾는 알고리즘이다.여기서 중요한 것은 그래프를 사이클이 생기면 안 된다는 것이다.사이클이 존재하면 가중치의 합이 최소가 될 수 없기 때문이다.또한 정점의 개수가 V라고 하면 정점을 최소 신장 트리를 구성하는 간선의 개수는 무조건 V-1개..