[백준 #15686]: 치킨 배달(python)

백준#15686:치킨 배달

import sys
from itertools import combinations

input = sys.stdin.readline

rowcol_index, M  = map(int,input().strip().split())
village = [list(map(int, input().split())) for _ in range(rowcol_index)]

home_list=[]
chicken_list=[]
for row in range(rowcol_index):
    for col in range(rowcol_index):
        if village[row][col] == 1:
            home_list.append((row,col))
        elif village[row][col] == 2:
            chicken_list.append((row,col))

result = float('inf')  
for choice in combinations(chicken_list, M): 
    song = 0            
    for i in home_list: 
        chicken_len = float('inf')   
        for j in range(M):
            chicken_len = min(chicken_len, abs(i[0] - choice[j][0]) + abs(i[1] - choice[j][1]))
        song += chicken_len
    result = min(result, song)
print(result)

해당 문제는 굉장히 간단한 문제이다. 선정할 수 있는 치킨집에 대한 모든 경우의수를 조사한뒤 각각의 집의 거리를 조사한다. 그 뒤 가장 짧은 거리를 계속해서 더해주어 선정한 치킨집에 대한 치킨거리를 구한 뒤 치킨 집에 대한 모든 경우의수를 이용하여 치킨거리를 구하면 된다.