[BOJ - 1647] 도시 분할 계획 ( 순수 C언어 )

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 

문제를 제대로 읽고 그림을 그려보면서 이해해야 조금 편할것 같다는 생각을 했다.

지문에는

"마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다."

라고 되어있는데 이게 제일 큰 함정이 아닐까?

일단 모든 도시를 MST 알고리즘을 통해 최적하게 먼저 만들어보자.

간단하게, 

이런 그림을 상상해보면, 쉬울것이다.

이러한 노드 들을 두 그룹으로 나눈다 라고 하는것은 저 선들 중 아무거나 하나 끊으면 되는 상태가 된다.

하지만, 여기서 두 그룹으로 나누되 제일 적은 값을 찾으라고 지문에 제시되어있다.

그렇기 때문에, 점들을 최적으로 이어주는 선들의 그룹 중 가장 길이가 큰 선을 빼주면

답을 구할수 있게된다.

코드는 다음과 같다.