[백준 15686 치킨 배달] - 파이썬 풀이 (골드 5)

https://www.acmicpc.net/problem/15686

---

문제 요약

치킨 거리 = 집과 가장 가까운 치킨 거리 = |x1-x2| + |y1-y2|
도시의 치킨 거리 = 모든 집의 치킨 거리의 합
도시의 치킨거리가 가장 작게 되도록 치킨집 M개만 남겼을 때의 도시의 치킨거리를 구하라.

---

풀이

m개의 치킨 집을 남기는 조합에 대해서, 도시의 치킨 거리가 최소가 되는 조합에서의 도시의 치킨 거리를 리턴한다.

# 백준 15686 치킨 배달 골드5 https://www.acmicpc.net/problem/15686
# 치킨거리: 집과 가장 가까운 치킨집까지의 거리 = |x1-x2| + |y1-y2|
# 도시의 치킨거리 = 모든 집의 치킨 거리의 합
# 도시의 치킨거리가 가장 작게 되도록 치킨집 M개만 남겼을 때의 도시의 치킨거리를 구하라.
# 0=빈칸, 1=집, 2=치킨집
from itertools import combinations
n, m = map(int, input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

house = []
chicken = []

for i in range(n):
    for j in range(n):
        # 집
        if board[i][j] == 1:
            house.append((i, j))
        # 치킨
        elif board[i][j] == 2:
            chicken.append((i, j)) 

result = 1e9
# m개의 치킨집 고르기
for comb in combinations(chicken, m):
    total_distance = 0
    for h in house:
        distance = 1e9
        # 어떤 집 h와 각 치킨집과의 최단 치킨 거리 구하기
        for j in range(m):
            distance = min(distance, abs(h[0] - comb[j][0]) + abs(h[1] - comb[j][1]))
        # 각 집의 치킨거리의 합
        total_distance += distance
    result = min(result, total_distance)

print(result)