치킨 배달

이것 또한 구현문제였다. 그냥 치킨집을 없애는 경우의 수를 조합으로 구해서 문제의 조건대로만 푸는 문제였는데 왜 이코테에서는 이게 기둥과 보 문제보다 더 어려운 난이도로 표시되었는지 의문이다... 푸는데 30분도 안걸린 것 같다.

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

from itertools import combinations

n, m = map(int, input().split()) #m개 빼고 모두 폐업시켰을 때 최소 치킨거리가 나오도록

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

#도시의 치킨집 개수를 구하고 m이 될떼까지 줄이는 모든 경우의 수에서 치킨거리 확인
#좌표로 풀어야 할 듯
chickens = [] #치킨집 좌표
houses = [] #집좌표
for x in range(len(city)):
    for y in range(len(city)):
        if city[x][y] == 2:
            chickens.append((x, y))
        elif city[x][y] == 1:
            houses.append((x, y))
distances = [] #치킨 거리 담을 리스트
chicken_distance = 0            
chickens_after = list(combinations(chickens, m)) #m개 빼고 없앤 치킨집의 경우의 수
for i in chickens_after:#집마다 치킨거리 계산
    for house in houses:
        min_dist = 99999
        for chickenzip in i:
            dist = (abs(house[0] - chickenzip[0]) + abs(house[1] - chickenzip[1]))
            if dist < min_dist:
                min_dist = dist
        chicken_distance += min_dist
    distances.append(chicken_distance)
    chicken_distance = 0

print(min(distances))