치킨 배달

💻 입력 조건

• 첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
• 둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.
• 도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

💻 출력 조건

• 첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

💻 입력 예시1

5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

💻 출력 예시1

5

💻 입력 예시2

5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2

💻 출력 예시2

10

💻 입력 예시3

5 1
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0

💻 출력 예시3

11

💻 입력 예시4

5 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1

💻 출력 예시4

32

📖 문제 해결
distance 함수와 min_distance 함수를 이용하여 치킨집과 집과의 거리를 구하고, 그중에서도 가장 가까운 치킨집과의 거리를 구할 수 있도록 하였습니다. 그리고 itertools 모듈 내의 combinations 함수를 이용하여 폐업시키지 않을 치킨집들의 가능한 모든 조합들에 대해서 치킨 거리의 합을 모두 계산할 수 있도록 하였고, 그중 가장 치킨 거리의 합이 작은 경우의 값을 출력할 수 있도록 하였습니다.

# n, m 입력받기
n, m = list(map(int,input().split()))

# 도시의 정보 입력받기
map_ = []

for i in range(n):
    map_.append(list(map(int,input().split())))
    
# house_coordis에 집들의 좌표를 저장
house_coordis = []

# chicken_coordis에 치킨집들의 좌표를 저장
chicken_coordis = []

for r_idx, row in enumerate(map_):
    for c_idx, col in enumerate(row):
        
        if map_[r_idx][c_idx] == 1:
            house_coordis.append((r_idx,c_idx))
            
        elif map_[r_idx][c_idx] == 2:
            chicken_coordis.append((r_idx,c_idx))

# 치킨 거리를 구하는 함수
def distance(coordi1,coordi2):
    return abs(coordi1[0]-coordi2[0]) + abs(coordi1[1]-coordi2[1])

# 가장 가까운 치킨집과의 거리를 구하는 함수
def min_distance(house_coordis, chicken_coordis):
    
    distance_count = 0
    
    for house_coordi in house_coordis:
        min_dis = []
        
        for chicken_coordi in chicken_coordis:
            min_dis.append(distance(house_coordi,chicken_coordi))
        
        distance_count += min(min_dis)
    
    return distance_count

from itertools import combinations

# 폐업시키지 않을 치킨집 m개를 고르는 모든 경우의 수 구하기
c_combinations = combinations(chicken_coordis, m)

# 모든 경우들에 대하여 치킨 거리를 구하고 answer 리스트에 추가
answer = []

for c_combi in c_combinations:
    answer.append(min_distance(house_coordis, c_combi))

# 치킨 거리의 최솟값을 출력
print(min(answer))