피자 배달 거리

문제 설명 도시는 N × N 크기의 격자로 구성되어 있고, 각 칸은 빈칸(0), 집(1), 피자집(2) 중 하나로 표시된다. 각 집은 피자를 받을 때 도시에 존재하는 피자집 중 가장 가까운 피자집 한 곳에서만 받게 되며, 이때의 거리를 그 집의 “피자 배달 거리”라고 한다.

하지만 최근 불경기로 인해 모든 피자집을 유지할 수는 없게 되었다. 그래서 시장은 M 개의 피자집만 선택해서 유지하고 나머지 피자집은 폐업시키려 한다.

이때 M 개의 피자집을 어떻게 고르느냐에 따라 각 집이 가장 가까운 피자집까지 가는 거리도 달라지게 된다. 전체 피자집들 중 M 개를 선택하여, 각 집에서 가장 가까운 피자집까지의 거리와 그 거리들의 총합을 최소화하라.

각 격자칸은 좌표(행 번호, 열 번호)로 표현된다. 거리 계산은 맨해튼 거리로, 두 위치 (x1, y1), (x2, y2)의 거리는 |x1 - x2| + |y1 - y2|로 구한다.

예를 들어 아래 사진에서 (1, 2)에 있는 집과 (2, 3)에 ...