[백준] 15686번: 치킨 배달

문제

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

풀이

combinations으로 가능한 모든 치킨집들의 조합을 모두 구하고
치킨 거리들을 구한다음 가장 작은 치킨 거리를 출력한다.

from itertools import combinations

N, M = map(int, input().rstrip().split(" "))
houses = []
bhcs = []
for row in range(N):
    row_data = list(map(int, input().rstrip().split(" ")))
    for col in range(N):
        if row_data[col] == 1:
            houses.append((row, col))
        elif row_data[col] == 2:
            bhcs.append((row, col))


def solution(N, M, houses, bhcs):
    answer = 987654321

    for bhc in combinations(bhcs, M):
        chi_distance = 0
        for y, x in houses:
            min_distance = 987654321
            for bhc_y, bhc_x in bhc:
                min_distance = min(min_distance, abs(y - bhc_y) + abs(x - bhc_x))
            chi_distance += min_distance
        answer = min(answer, chi_distance)
    print(answer)
    return


solution(N, M, houses, bhcs)