백준 15686: 치킨배달 (Python/파이썬)

빡구현.. 이거 맞나.. 분명 더 효율적인 방법이 있을 거 같은데 다시 풀어봐야겠음

import sys
from itertools import combinations
input = sys.stdin.readline

def find_min(M, now):
    if M == now:
        res = 0
        for r in distance:
            res += (min(r))
        return res

    min_dist = float('inf')
    for comb in combinations(range(now), m):
        temp = 0
        for i in range(len(houses)):
            temp += min(distance[i][j] for j in comb) #선택된 치킨 집 중 가장 가까운 데
        
        min_dist = min(temp, min_dist) # 모든 조합에 대해 실행
    return min_dist


n, m = map(int, input().split())
chickens = []
houses = []
town = []

r = 0
for i in range(n):
    row = list(map(int, input().split()))

    for idx, char in enumerate(row):
        if char == 1:
            houses.append((r, idx))
        elif char == 2:
            chickens.append((r, idx))

    town.append(row)
    r += 1

# 0: 빈칸, 1: 집, 2: 치킨집
# 거리는 abs(r1-r2) + abs(c1-c2)

distance = [[0] * len(chickens) for _ in range(len(houses))]

for i in range(len(houses)):
    for j in range(len(chickens)):
        distance[i][j] = abs(houses[i][0] - chickens[j][0]) + abs(houses[i][1] - chickens[j][1])

print(find_min(m, len(chickens)))