도시 분할 계획
📌문제마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을을 분할할 때는 각 분할된 마을 안에 집들이 서로 연결되도록 분할해야 한다.마을의 이장은 계획을 세우다 마을 안에 길이 너무 많다는 생각을 했다. 일단 분리된 두 마을 사이 길은 필요 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하는 프로그램을 작성하시오. 📌풀이전체 그래프에서 2개의 최소 신장 트리 만들어야 함크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤에 최소 신장 트리를 구성하는 간선 중..
코딩테스트
2024. 11. 14. 20:08