병원 거리 최소화하기

사람, 병원 혹은 빈 칸으로 이루어져 있는 n×n 크기의 도시가 주어집니다. 이 때, 각 사람의 병원 거리는 가장 가까운 병원까지의 거리를 의미하며, 두 격자 (x1,y1), (x2,y2) 사이의 거리는 ∣x2−x1∣+∣y2−y1∣으로 정의됩니다. 운영상의 이유로 m개의 병원만을 남겨두고 나머지를 폐업해야 할 때 남은 m개의 병원에 대한 각 사람들의 병원 거리의 총 합이 최소가 되도록 하려고 합니다.

예를 들어 아래의 그림과 같은 상황에서 하나의 병원만 남겨두려고 할 때