문제 출처 : https://www.acmicpc.net/problem/15686

---

문제 파악

NxN 도시가 있다. 왼쪽 위부터 (1,1) ... (N,N)
각 칸은 빈 칸 (0), 집 (1), 치킨 집(2) 중 하나이다.

치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리
각각의 집은 치킨 거리를 가지고 있다.

도시의 치킨 거리 : 모든 집의 치킨 거리의 합

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다고 한다.

치킨 집을 M개 만 남겨두고 나머지는 없앨 건데 도시의 치킨 거리 가 가장 작게 되게 하고 싶다. 이때 도시의 치킨 거리의 최솟값을 출력하라.

---

이 문제의 핵심은 치킨집 M개를 선택하고,모든 집에 대해 최소 치킨 거리 합을 계산하는 것이다.

치킨집이 최대 13개이므로, 완전탐색(DFS) 으로 가능해보인다.

DFS 깊이를 현재까지 선택한 치킨집 수(depth)로 두고,
한 단계씩 다음 치킨집을 선택하거나 건너뛴다.

M개를 모두 선택했을 때(depth == m),
각 집이 가장 가까운 치킨집까지의 거리를 구해 총합을 계산한다.

이 총합을 answer에 계속 갱신하면서 최소값을 찾는다.

해답 및 풀이

import sys
input = sys.stdin.readline

# --- 입력
N, M = map(int,input().split())

city = []
for i in range(N):
    row = list(map(int,input().split()))
    city.append(row)


# ---- 집, 치킨집 좌표 저장
houses = [] # 집의 좌표들을 저장해놓은 리스트 (r,c)
chicken_restaurants = [] # 치킨 집의 좌표들을 저장해놓은 리스트 (r,c)

for i in range(N):
    for j in range(N):
        if city[i][j] == 1:
            houses.append((i,j))
        if city[i][j] == 2:
            chicken_restaurants.append((i,j))

# ---- 맨허튼 거리 계산 함수 선언
def manhattan(a, b): # a, b는 각 (r1,c1), (r2,c2)
    r1,c1 = a[0],a[1]
    r2,c2 = b[0],b[1]

    return (abs(r1-r2) + abs(c1-c2))

# ----
answer = 1e9 # 최솟값을 구할때는 가장 큰 수로 초기화 해준다.
choosen_chicken_restaurants = []

def dfs(depth, idx): # depth: 지금 몇개의 치킨집을 선택했는가, idx : 다음 탐색을 시작할 치킨집의 인덱스
    global answer

    # 종료조건 : 폐업시키지 않을 치킨집 M개를 다 골랐다면
    if depth == M:
        city_chicken_dist = 0 # 도시의 치킨 거리
        for h in houses:
            temp1 = 1e9
            for c in choosen_chicken_restaurants:
                dist = manhattan(h,c) 
                temp1 = min(temp1, dist)
            city_chicken_dist += temp1
        answer = min(answer,city_chicken_dist)
        return
    
    # 아직 M개를 다 고르지 안았다면
    for i in range(idx, len(chicken_restaurants)): 
        choosen_chicken_restaurants.append(chicken_restaurants[i])
        dfs(depth+1, i+1)
        choosen_chicken_restaurants.pop()

dfs(0,0)
print(answer)

참고 블로그 : https://jjung0326.tistory.com/95