백준1 [백준] 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 전체 그래프를 2개로 나누는데 그 나눠진 그래프 안에서는 서로 다 연결이 돼 있어야 한다는 얘기..... (근데 대체 원숭이🙊 얘기는 왜 나온거지???) 📖접근 방법 크루스칼 알고리즘을 이용해서 최소신장 트리를 하나 만듬 그 중에서 가장 비싼 간선을 하나 없앤다 (그래야 최소 비용이 되니까!) 그러면 자연스럽게 그래프가 2개로 분리된다! 그리고! import .. 2021. 9. 25. 이전 1 다음
