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

1. 코드

import sys
from collections import defaultdict
from itertools import combinations

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

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 
0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며,
적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

-> M이 최대 13개라는 조건을 보고 조합 라이브러리 사용
"""
min_ans = 99999
chicken_cnt = 0

house = []
d = defaultdict(tuple)
n, m = map(int, sys.stdin.readline().rstrip().split())
og_graph = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
for i in range(n):
    for j in range(n):
        if og_graph[i][j] == 2:
            chicken_cnt += 1
            d[chicken_cnt] = (i, j)
        elif og_graph[i][j] == 1:
            house.append((i, j))

# 각 open_chicken 는 폐업하지 않고 남아있는 m 개 묶음의 치킨집의 번호 튜플이다.
for open_chicken in list(combinations(range(1, chicken_cnt + 1), m)):
    ans = 0
    for h in house:
        dis = 9999
        h_x, h_y = h[0], h[1]

        for c in open_chicken:
            c_x, c_y = d[c]
            dis = min(abs(h_x - c_x) + abs(h_y - c_y), dis)
        ans += dis
    min_ans = min(ans, min_ans)
print(min_ans)