문제 링크 : https://www.acmicpc.net/problem/1414 문제를 살펴보면 해결하는 방법은 최소신장 트리를 이용하면 간단히 해결할 수 있다.주의해야 하는 것은 문자를 정수로 변경하는 것과A -> A로 돌아오는 간선은 제외하고 생각해야 한다는 것이다. 예제 입력 1번을 그래프로 표현하면 위와 같다. 문제를 해결하는 과정은 아래와 같다.1. 주어진 간선(랜선)의 총합을 구한다 (sum)2. 자기 자신에게 돌아오는 간선(랜선)을 제외하고 나머지 간선을 가중치를 기준 오름차순으로 정렬한다.3. MST알고리즘을 통해 모든 정점을 잇는 거리의 최단거리를 구한다(minSum)4. 만약 고른 간선의 길이가 주어진 정점의 개수 - 1 개가 아니라면 -1을 출력하고, 맞다면 sum - minSum 값..

문제 링크 : 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개..