[백준] 치킨배달 15686 (브루트포스) Python

집 리스트, 치킨집 리스트를 구하고 주어진 M(도시에 있을 수 있는 최대의 치킨집 수)에 따라 치킨집을 조합한다.

 

조합된 치킨집 리스트에 따라 각 집별의 치킨거리를 구한다. (각 조합별의 치킨거리의 합)

 

조합별 집과의 치킨거리의 합을 구한 것 중 최소 값을 구한다.

 

import itertools
n,m = map(int, input().strip().split())
 
lists = []
home = []
chicken = []
 
for i in range(n):
    lists.append(list(map(int, input().strip().split())))
 
for i in range(n):
    for j in range(n):
        if lists[i][j] == 1:
            home.append([i,j])
        if lists[i][j] == 2:
            chicken.append([i,j])
 
chicken_list = list(itertools.combinations(chicken, m))
 
answer = []
for i in chicken_list:
    total = 0
    for h in home:
        minn = 10000000
        for j in i:
            minn = min(minn, abs(j[0] - h[0]) + abs(j[1] - h[1]))
        total += minn
    answer.append(total)
print(min(answer))