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

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

15686번: 치킨 배달

브루트 포스 문제다.

 

N이 <50이라 안될 거 같아도 사실 신경 써야 하는 건 치킨집의 개수고 M <=13 이므로 2^13 == 8192 정도에 N*M 이니까 combination으로 전부 탐색해도 된다.

 

그 후 거리를 구하는데, Manhattan distance(L1) 로 구해야 한다. 

 

 

집 개수랑 치킨집 개수랑 헷갈리지 말자. 

 

 

import sys
from itertools import combinations


n, m = [int(i) for i in sys.stdin.readline().split()]

arr = []
for _ in range(n):
    arr.append([int(i) for i in sys.stdin.readline().split()])
house = []
chicken = []

for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            house.append((i, j))
        elif arr[i][j] == 2:
            chicken.append((i, j))


ans = []
for p in combinations(chicken, m):
    ret = 0
    for h in house:
        minval = 991234
        for c in p:
            minval = min(abs(h[0]-c[0]) + abs(h[1]-c[1]), minval)

        ret += minval

    ans.append(ret)

print(min(ans))