728x90 최소스패닝트리1 [python] 백준 1647 도시 분할 계획 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 문제 해결 조금 고민하면 한 번 노드를 다 이은 후 가장 긴 길이를 빼면 되지 않을까? 싶은 생각을 할 수 있다. 하지만 이 때 가장 긴 길이가 짧아서 나눌 때 최소 길이가 되지 않을 수 있지 않나? 생각을 하게 되었다. 하지만 정렬(sort)를 이용하여 가장 유지비용이 짧은 두 노드부터 이어가며 모든 노드를 다 이은 다음 가장 나중에 이은 노드를 뺀다면 최소.. 2024. 3. 1. 이전 1 다음 728x90
