15686-치킨배달

www.acmicpc.net/problem/15686

1. 폐업시키지 않을 치킨집의 경우의 수 순열 리스트 cases

2. 각 경우에서 집마다 최단거리들의 합을 구함 total_rst

3. 매 경우마다 더 작은 값으로 업데이트 rst

import sys
from itertools import combinations

def total_distance(chicken_shops):
    rsts = []
    # 모든 집에 위치에서 제일 가까운 치킨집 찾자
    for home in homes:
        hy = home[0]
        hx = home[1]
        # 모든 치킨집중 가장 가까운 위치를 더하자
        min_dst = int(1e9)
        for shop_location in chicken_shops:
            sy = shop_location[0]
            sx = shop_location[1]
            min_dst = min(min_dst, abs(hy-sy) + abs(hx - sx))
        rsts.append(min_dst)
    # 모든 집에서 가장 가까운 치킨집과의 거리들 리스트 rsts
    total_dst = sum(rsts)
    return total_dst

n, m = map(int,input().split())
arr = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]

# 치킨집 위치 정보들
shops = []
for i in range(n):
    for j in range(n):
        if arr[i][j] == 2:
            shops.append([i,j])
# 집 위치 정보들
homes = []
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            homes.append([i,j])
# 폐업시키지 않을 치킨집 경우의 수들
cases = []
for i in list(combinations(shops,m)):
    cases.append(i)

# 폐업시키지 않을 각 경우의 수마다 최단거리의 합 추출
rst = int(1e9)
for case in cases:
    # 해당경우의 수에서 기존 최단거리 합보다 더 작다면 업데이트
    rst = min(total_distance(case),rst)

print(rst)