[BOJ] 15686. 치킨배달(python)

📌문제

💪아이디어

1. m개 치킨집 고르기
   순서와 중복이 없는 combination을 통해 전체 치킨집 중 m개의 치킨집을 고른다.
   

2. 치킨 거리 구하기
   각 집마다 고른 m개의 치킨집에서 가장 가까운 치킨집과의 거리를 구한다.
   

3. 도시의 치킨 거리 구하기
   

🥂코드

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

def chickenRoad(house, chicken):
    hx, hy = house
    cx, cy = chicken
    return abs(hx-cx) + abs(hy-cy)

houses = []
chickenShops = []

n, m = map(int, input().split())
for i in range(n):
    town = input().split()
    for j in range(n):
        if town[j] == '1': houses.append((i+1,j+1))
        elif town[j] == '2': chickenShops.append((i+1,j+1))

answer = float('inf')
for c in combinations(chickenShops,m):
    combiRoad = 0
    for h in houses:
        streetPerHouse = float('inf')
        for i in range(m):
            streetPerHouse = min(streetPerHouse, chickenRoad(h,c[i]))
        combiRoad += streetPerHouse
    answer = min(answer,combiRoad)
print(answer)