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 풀이 사용한 알고리즘 : 크루스칼 알고리즘 풀이전략 문제는 최소 신장트리를 만들 것을 요구하고 있다. 최소 신장트리란 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 문제에서는 마을 내부의 모든 집이 연결되면서, 비용이 최소가 되도록 길을 연결했을 경우의 비용을 요구하고있기 때문에, 최소 신장트리를 만들고, 만..
