[Python] 백준 15686. 치킨배달

 

 

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

 

 

풀이

집과 치킨집의 좌표를 저장해두고

치킨집 m개로 만들 수 있는 조합을 활용하여 치킨 거리가 최소가 되는 조합을 구한다.

 

코드

from itertools import combinations
import sys
input = sys.stdin.readline
n, m = map(int, input().split()) 
arr = [list(map(int, input().split())) for _ in range(n)]
house = []
chick = []
for i in range(n):
    for j in range(n):
        # 집이면
        if arr[i][j] == 1:
            # 좌표를 저장한다
            house.append((i,j))
        elif arr[i][j] == 2:
            # 좌표를 저장한다
            chick.append((i,j))

comb = tuple(combinations(chick,m))
temp_ls = []
for i in comb:
    temp = 0
    for k in house:
        min_val = int(1e9)
        for j in i:
            min_val = min(min_val, abs(k[0]-j[0]) + abs(k[1]-j[1]))
        temp += min_val
    temp_ls.append(temp)

print(min(temp_ls))