[백준] 치킨 배달.py

import sys
import math
from itertools import combinations

n, m = map(int, sys.stdin.readline().split())
# 치킨집 위치, 집 위치
chicken, house = [], []
# 치킨집 위치 / 집 위치 저장
for y in range(n):
    tmp = list(map(int, sys.stdin.readline().split()))
    for x in range(len(tmp)):
        if tmp[x] == 1:
            house.append((y,x))
        elif tmp[x] == 2:
            chicken.append((y,x))
            
# 치킨집 중 m개의 치킨집을 선택하는 경우의 수
candidate = list(combinations(chicken, m))

# 거리 최소값 구하기.
# 각 집 위치마다 모든 치킨집과의 거리를 구하고, 최솟값만 result에 더한다.
def get_min_distance(candidate, house):
    result = 0
    for hy, hx in house:
        tmp_min = math.inf
        for y, x in candidate:
            if abs(hy-y) + abs(hx-x) < tmp_min:
                tmp_min = abs(hy-y)+ abs(hx-x)
        result += tmp_min
    return result

# 거리의 최솟값
min_result = math.inf
for i in candidate:
    result = get_min_distance(list(i),house)
    if min_result > result:
        min_result = result
print(min_result)