최소신장트리

자바(Java) 알고리즘 문제풀이 최소 스패닝 트리[백준 / 크루스칼(그리디)]

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 코드 이 문제는 최소 신장트리를 구하는 문제인데, 크루스칼 알고리즘을 사용하면 해결되는 문제이다. 크루스칼 알고리즘이란, 그래프 내 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용된다. 쉽게 말해 그래프를 회로가 없는 트리로 만들면 되는 것. 그래프 내의 모든 정점들 중, 가장 적은 비용을 가진 간선부터 연결을 시작하고 연결하기 전에 해당 ..