백준 15686번 치킨 배달

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

15686번: 치킨 배달

단순히 브루트 포스로 해결이 되는 문제이다...

 

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

N, M = map(int,input().split())

matrix = [list(map(int,input().split())) for _ in range(N)]

house_position = []
chicken_position = []

for idx1, row in enumerate(matrix):
    for idx2, k in enumerate(row):
        if k == 1:
            house_position.append((idx1,idx2))
        if k == 2:
            chicken_position.append((idx1,idx2))

chicken_comb = list(combinations(chicken_position, M))

final_result = []
for each0 in chicken_comb:

    chicken_distance = []

    for each1 in house_position:
        tmp = []
        for each2 in each0:
            tmp.append(abs(each1[0] - each2[0]) + abs(each1[1] - each2[1]))

        chicken_distance.append(min(tmp))

    final_result.append(sum(chicken_distance))

print(min(final_result))