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

15686번: 치킨 배달

---

 

M만큼 치킨집 조합을 구하여 치킨거리를 노동으로 다 구해보면 된다.

 

1. 집과 치킨집 좌표를 house와 chicken에 저장한다.
2. chicken 을 조합으로 chicomb를 만들어준다.
3. house 별로 돌리면서 가장 짧은 치킨 거리를 구한다.
4. 가장 짧은 도시의 치킨 거리를 출력한다.

 

import sys
from itertools import combinations
input = sys.stdin.readline

N, M = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().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])

result = sys.maxsize
for chicomb in combinations(chicken, M):
    mindistance = 0
    for h in house:
        _min = sys.maxsize
        for c in chicomb:
            distance = abs(h[0]-c[0])+abs(h[1]-c[1])
            _min = min(distance, _min)
        mindistance += _min
    result = min(mindistance, result)


print(result)