백준 도시분할계획 16471 [6개월 안에 백준 플래티넘 달성하기] 17. 도시 분할 계획 1197 도시 분할 계획 문제 풀이 문제의 조건은 다음과 같습니다. 양방향이다. 마을을 두 개의 분리된 마을로 분할한다. 마을과 마을 사이에는 길이 존재하지 않는다. 마을 내부의 임의의 두 집 사이에는 경로가 항상 존재한다. 마을 내부에는 최소 하나 이상의 집이 있다. 위 조건을 만족하면서 유지비의 합이 최소여야 한다. 조건이 다소 많아 처음에는 흠칫하였지만 임의의 두 집 사이에는 경로가 항상 존재하며 최소 유지비를 만들어야 된다는 것에서 쉽게 최소 신장 트리 알고리즘을 생각할 수 있었습니다. 풀이 방법은 다음과 같습니다. 전체 집을 대상으로 최소 신장 트리를 구합니다. (= 경로 최소화 작업) 간선들 중에 가장 큰 유지비를 가진 가중치를 하나 제거해 줍니다.(= 마을 분리 작업) 위의 두 단계만으로 문제를 해결.. 2024. 1. 2. 이전 1 다음 반응형
