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

도시에 치킨집이 있는데 m개까지 치킨집을 폐업시키는 슬픈 문제이다.
치킨집과 가정집의 위치가 2차원 배열로 주어지고, dx+dy만큼을 거리로 계산한다. 이때 가정집에서 가장 가까운 치킨집의 거리 합(치킨 거리)이 최소가 되게 하는 문제이다.

Python

from itertools import combinations

n, m = map(int, input().split())

chicks = []
home = []
for i in range(n):
  row = list(input().split())
  for j in range(n):
    if row[j] == '1':
      home.append((i, j))
    elif row[j] == '2':
      chicks.append((i, j))

ans = 2 * n * 1000
for c in combinations(chicks, m):
  local_len = 0
  for h in home:
    min_len = 2 * n * 1000
    for ch in c:
      min_len = min(min_len, abs(h[0] - ch[0]) + abs(h[1] - ch[1]))
    local_len+= min_len
  ans = min(ans, local_len)
  
print(ans)

치킨집과 가정집의 좌표를 따로 저장하였다.
그리고 치킨집에서 m개만큼 뽑는 조합을 실행해서 각 경우마다 치킨거리를 구하고 ans에 최소값을 업데이트 했다.