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

풀이

• m개의 치킨 집을 선택할 때 치킨집과 일반집 사이의 치킨거리(일반집과 가장 가까운 치킨집과의 거리)의 합을 구해야 함.
• 먼저 치킨집 일반집의 좌표(i,j)를 puradak과 house리스트에 저장
• combinations를 이용해서 치킨집을 m개 선택 했을 때의 조합을 구함
• 순회를 돌면서 일반집 하나와 치킨집 사이의 최단거리를 치킨거리에 추가
• 조합에서 구한 치킨 거리 중 가장 작은 치킨거리를 출력

코드

import sys
from itertools import combinations
input = sys.stdin.readline
n,m = map(int, input().split())
maps = [list(map(int,input().split())) for _ in range(n)]
# 치킨집과 일반집 위치 구하고, 각 위치에 대해서 치킨거리를 구해야함.
puradak = []
house = []
for i in range(n):
    for j in range(n):
        if maps[i][j] == 1:
            house.append([i,j])
        elif maps[i][j] == 2:
            puradak.append([i,j])
# 치킨집을 m개 선택했을때 조합
combs = list(combinations(puradak, m))
cand = []

for comb in combs:
    answer = 0
    for h in house:
        x1, y1 = h
        dist = int(1e9)
        for c in comb:
            x2, y2 = c
            dist = min(dist, abs(x1-x2) + abs(y1-y2))
        answer+=dist
    cand.append(answer)
print(min(cand))