1. 문제 설명

치킨 배달

2. 문제 분석

n개 중 m개를 순서에 상관없이 고른다면 조합 combinations를 사용할 수 있다.

• 모든 치킨 집 중 m개의 치킨 집을 택하고, 각 집의 최단 치킨 거리의 합을 모두 카운트하자. 가능한 조합에서 만들어진 치킨 거리 중 가장 작은 값을 리턴한다.

3. 나의 풀이

from itertools import combinations

n, m = map(int, input().split())

house = []
chicken = []

for i in range(n):
    for idx, j in enumerate(list(map(int, input().split()))):
        if j == 1: house.append([i, idx])
        elif j == 2: chicken.append([i, idx])
# 집, 치킨 집 좌표 입력

totals = []

combis = list(combinations(chicken, m))
# 치킨 집 중 m개를 선택하는 조합
for combi in combis:
    total = 0
    for h in house:
        h_row, h_col = h
        distance = 9999999
        for comb in combi:
            c_row, c_col = comb
            distance = min(distance, abs(h_row-c_row)+abs(h_col-c_col))
        # 주어진 치킨 집 중 각 집에서 가장 가까운 치킨 거리를 찾는다.
        total += distance
        # 모든 집의 치킨 거리의 합을 total이라 할 때
    totals.append(total)
    # 이 치킨 집 조합에서 생기는 치킨 거리의 합을 입력한다.
print(min(totals))
# 만들어진 치킨 거리 중 최솟값을 return