✅문제 요약

1. nxn 도시
2. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나
3. 치킨 거리: 집과 가장 가까운 치킨집 사이의 거리
4. M개의 치킨집을 제외하고 모두 폐업시켰을 때 도시의 치킨거리의 최솟값 출력

✅문제 풀이

M개를 무작위로 골라서 모든 경우를 찾아야 하기 때문에 완전탐색+dfs 즉 조합 문제이다.

from collections import deque
N, M = map(int, input().split())                                # 도시 크기, 남은 치킨집 수
arr = [list(map(int, input().split())) for _ in range(N)]       # 도시


def dfs(n, i):      # n: 고른 치킨집 수 i: 고른 치킨집 번호
    global result
    val = 0
    # 모든 치킨집을 골랐다면 치킨거리 계산
    if n == M:
        for h in house:
            hr, hc = h[0], h[1]
            dist = 2*N

            for c in select:
                cr, cc = c[0], c[1]
                tmp = abs(hr-cr) + abs(hc-cc)
                if tmp < dist:
                    dist = tmp
            val += dist

        if val < result:
            result = min(val, result)
            return
	# 고른 치킨 집을 제외하고 dfs
    for idx in range(i, K):
        select.append(chicken[idx])
        dfs(n+1, idx+1)
        select.pop()

chicken = deque([])
house = deque([])

select = deque([])
for a in range(N):
    for b in range(N):
        if arr[a][b] == 1:        # 집 위치 추가
            house.append((a, b))
        elif arr[a][b] == 2:      # 치킨집 위치 추가
            chicken.append((a, b))

K = len(chicken)             # 총 치킨집 수
result = N*2*len(house)      # 총 치킨거리 임의의 큰 값

# 조합 시작
for t in range(K):
    dfs(0, t)

print(result)