문제 난이도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. 간선을 하나씩 선택하여 사이클이 생기지 않을 때 연결하여 모든 노드가 연결될 때 까지 반복한..