[12-07 구현 문제] 치킨 배달

최근 보고 있는 책인  '이것이 코딩테스트다 with 파이썬 편_나동빈_한빛미디어' 에 있는 문제이다.

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

 

문제는 백준에 있다.

www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

 

 

import sys
import itertools

input = sys.stdin.readline

n,m = map(int,input().split())
board = []
INF = int(1e9)

for i in range(n):
    board.append(list(map(int,input().split())))

home_arr = []
chicken_arr =[]
for i in range(n):
    for j in range(n):
        if board[i][j] == 1:
            home_arr.append([i,j])
        elif board[i][j]==2:
            chicken_arr.append([i,j])


chick_combi = list(itertools.combinations(chicken_arr,m))

total = INF
for chicken in chick_combi:
    min_total = 0
    for home in home_arr:
        min_temp = INF
        for temp in chicken :
            distance = abs(temp[0]-home[0]) + abs(temp[1]-home[1])
            min_temp = min(min_temp,distance)

        min_total += min_temp

    total = min(total,min_total)


print(total)