[n15686] 치킨 배달 in python

---

보자마자 조합을 써야하는 문제인가 싶었다.

일단 집 위치와 치킨집 위치를 

각 배열에 정리해주었다.

탐색하기 편하도록!

 

combinations 함수를 이용하여m개의 치킨집 경우의 수를 뽑아낸다.

 

도시의 치킨거리가 가장 작게되는 경우의 수를 구하는 거니까.min함수를 이용해야 한다.

 

answer의 초기값은 int형 max값으로 설정 (1 * 10^9)만약 answer의 값이 sum보다 크다면answer에는 sum값을 집어넣어주면 된다.

 

 

from itertools import combinations

n, m = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(n)]
houses = []
chickens = []
for i in range(n):
    for j in range(n):
        if array[i][j] == 1:
            houses.append((i, j))
        elif array[i][j] == 2:
            chickens.append((i, j))
answer = 1000000000
for chicken in combinations(chickens, m):  # chicken에서 최대 m개의 치킨집을 고르는 수
    sum = 0
    for house in houses:
        sum += min([abs(house[0] - i[0]) + abs(house[1] - i[1]) for i in chicken])
    if answer>sum:
        answer=min(answer,sum)

print(answer)