1647
-
[백준]1647: 도시 분할 계획 - JAVA문제풀이/백준 2021. 3. 1. 18:34
[백준]1647: 도시 분할 계획 www.acmicpc.net/problem/16471647번: 도시 분할 계획첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집www.acmicpc.net풀이집이 모두 연결되어 있는 상태에서 연결된 집을 두개의 마을로 나누는 문제이다. MST알고리즘을 사용하여 풀면 된다.MST알고리즘은 최소 간선을 선택해서 모든 노드를 연결한 경로를 찾는 알고리즘이다. 이 문제의 어려웠던 점은 하나로 연결된 집을 간선의 비용을 최소로 갖는 두 개의 마을로 나누는 부분이다. 처음에는 어떻게 해야 하나 감이 안잡혔지만..