[백준] 1647번:도시 분할 계획 (Java 자바)

문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 및 소스코드 MST를 사용해서 최소 가중치로 그래프를 만들어 준 후, 가장 가중치가 큰 간선 하나를 빼면 유지비가 최소가 되는 두 마을을 만들 수 있다. 따라서 원래의 MST는 n-1번의 간선을 만들어줬다면, 이 문제는 n-2번의 간선만 만들어주면 된다. 크루스칼 알고리즘 사용 (320940kb, 1160ms) import java.io.Buffer..
Coding - Algo/Java 2021. 9. 30. 15:28
1