문제 난이도GOLD I (링크)   문제 풀이각각의 독립된 섬들을 최단 거리로 연결하고 싶을 때, 놓을 수 있는 다리의 총 길이의 최소값을 구하는 문제.역시나 최소 신장 트리를 응용한 문제가 되겠다. 이번에는 각 간선을 구하는 것과 더불어, 이 섬이 어느 정점인지를 구하는 것도 필요하다. 결국엔 두 정점 사이의 간선을 구해서 문제를 풀어야하기 때문이다.  위의 그림처럼 문제에서 요한 3가지 올바르지 않은 방법과 함께, 추가로 두 가지만 주의한다면 쉽게 풀 수 있다. 처음 다른 섬을 만났을 때 만족하지 않는 조건이라면 바로 빠져나올 것.부끄럽게도 처음 코드를 완성시켰을 때,  다른 섬을 만났을 때, 종료 조건을 부족하게 작성하여 아래 그림처럼 더이상 탐색하지 못함에도 불구하고 탐색을 시켰다.   Union..

문제 난이도GOLD III   1774번 풀이간선의 가중치가 주어지지 않아 간선의 가중치를 구하는 로직만 추가해준다면 쉽게 문제를 해결할 수 있다. 이 문제에서 간선의 가중치는 2차원에 있는 신들의 위치 사이의 거리를 구하는 것으로, 아래 공식처럼 유클리드 거리 계산 방법을 이용하면 쉽게 가중치를 구할 수 있다.   위 공식을 코드로 나타낸다면 아래와 같다. private static double calCost(int x1, int x2, int y1, int y2) {    return Math.sqrt(Math.pow(x1 - y1, 2) + Math.pow(x2 - y2, 2));}       크루스칼(Kruskal) 알고리즘 (with. 백준 1197번 최소 스패닝 트리)크루스칼 알고리즘 (Kru..

크루스칼 알고리즘 (Kruskal Algorithm)크루스칼 알고리즘(Kruskal Algorithm)이란 최소 신장 트리(Minimum Spanning Tree)를 찾기 위해 사용되는 알고리즘이다. 신장 트리(Spanning Tree)그래프 내의 모든 정점을 포함하는 트리 최소 신장 트리(Minimum Spanning Tree)신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리   최소 신장 트리를 찾기 위해 모든 간선을 가중치에 따라 오름차순으로 정렬하는 아이디어를 사용하여 효과적으로 MST를 구할 수 있게 된다.세부적인 구현 방법은 다음과 같다. 1. 모든 간선을 가중치에 따라 오름차순 정렬한다.2. 간선을 하나씩 선택하여 사이클이 생기지 않을 때 연결하여 모든 노드가 연결될 때 까지 반복한..