[BOJ/백준] 15686 치킨 배달 파이썬

문제 링크 : https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

치킨집을 m개를 고르고 각 집마다 가장 가까운 치킨집과의 거리를 계산해서 합의 최솟값을 구하는 문제이다.

조합으로 치킨집을 m개 고르고 집마다 치킨집과의 거리를 계산해서 최솟값을 구하면 된다.

 

from sys import stdin
from itertools import combinations

input = stdin.readline

n,m = map(int, input().split())
board = []
home = []
chicken = []
for x in range(n):
    board.append(input().strip().split())
    for y in range(n):
        if board[x][y] == '1':
            home.append((x,y))
        elif board[x][y] == '2':
            chicken.append((x,y))

def solv():
    answer = 9876543210

    for comb in combinations(chicken,m):
        total = 0
        for sx,sy in home:
            length = 9876543210
            for ex,ey in comb:
                length = min(length,abs(sx-ex)+abs(sy-ey))
            total += length
        answer = min(answer,total)

    print(answer)
solv()