이번 문제는 도시 전체를 순회하며 각 집의 인덱스와 치킨집의 인덱스를 따로 저장한 후, 치킨집들을 itertools의 combinations를 이용하여 m개씩으로 조합한 리스트를 순회하며 각 집들과의 거리 중 가장 짧은 거리를 누적시켜 그 값을 비교하여 가장 작은 값을 출력하도록 작성하였다.

• n, m을 입력받는다.
• 도시의 정보를 입력받을 리스트 town을 선언한다.
• 각 집의 인덱스를 저장할 리스트 home을 선언한다.
• 치킨집의 인덱스를 저장할 리스트 chicken을 선언한다.
• n번 반복하며 town을 입력받는다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> n번 반복하는 j에 대한 for문을 돌린다.
  --> 만약 town[i][j]가 1일 경우, home에 (i, j)를 넣는다.
  --> 만약 town[i][j]가 2일 경우, chicken에 (i, j)를 넣는다.
• 거리를 구하는 함수를 get_dist를 frm, t를 인자로 갖도록 선언한다.
  -> frm[0]-t[0]의 절댓값 + frm[1]-t[1]의 절댓값을 반환한다.
• 최댓값을 저장하는 변수 INF에 sys.maxsize를 저장한다.
• answer를 INF로 선언한다.
• combinations(chicken, m)을 순회하는 chk에 대한 for문을 돌린다.
  -> 거리의 총 합을 저장할 변수 sumv를 0으로 선언한다.
  -> home을 순회하는 h에 대한 for문을 돌린다.
  --> sumv에 h와 chk안의 치킨집의 거리 중 최솟값을 더한다.
  --> 만약 answer가 sumv보다 작거나 같을 경우, 반복문을 종료한다.
  -> sumv가 answer보다 작을 경우, answer를 sumv로 갱신한다.
• answer를 출력한다.

Code

import sys
from itertools import combinations
n, m=map(int, input().split())
town=[]
home=[]
chicken=[]
for _ in range(n):
    town.append(list(map(int, input().split())))
for i in range(n):
    for j in range(n):
        if town[i][j]==1:
            home.append((i, j))
        if town[i][j]==2:
            chicken.append((i, j))
def get_dist(frm, t):
    return abs(frm[0]-t[0])+abs(frm[1]-t[1])
INF=sys.maxsize
answer=INF
for chk in combinations(chicken, m):
    sumv=0
    for h in home:
        sumv+=min([get_dist(h, i) for i in chk])
        if answer<=sumv: break
    if sumv<answer:
        answer=sumv
print(answer)