[코딩인터뷰] 백준 15686번

백준 15686번

def set_min(chicken):
    global n
    global city
    global answer

    total = 0
    for i in range(n):
        for j in range(n):
            if city[i][j] == 1:
                dists = []
                for c in chicken:
                    dists.append(abs(c[0] - i) + abs(c[1] - j))
                total += min(dists)

    if total < answer:
        answer = total

def dfs(chicken, x, y):
    global n
    global m
    global city

    if len(chicken) == m:
        set_min(chicken)
        return

    for i in range(x, n):
        t = 0 if x != i else y
        for j in range(t, n):
            if city[i][j] == 2:
                chicken.append((i, j))
                if j - 1 < n:
                    dfs(chicken, i, j + 1)
                else:
                    dfs(chicken, i + 1, 0)
                chicken.pop()

# 빈칸 / 집 / 치킨집
cell = (0, 1, 2)

# 도시의 치킨거리 = SUM(집의 치킨거리)
# 최대 M 치킨집 / 나머지 폐업

n, m = map(int, input().split())
city = []
for _ in range(n):
    city.append(list(map(int, input().split())))

answer = 10 ** 10
dfs([], 0, 0)
print(answer)