치킨 배달

이 문제는 치킨집의 개수를 M개로 유지한 채 사람들의 집과 치킨집의 거리를 최소화하게 치킨집을 유지하는 문제이다. 즉 기존에 5개의 치킨집이 있었는데 M이 3이라면 치킨집 5개에서 3개로 줄이는 것이고, 5개중 3개의 치킨집 위치를 사람들의 집과 가장 가깝게 배치했을 때 집과 치킨집의 거리르 구하면 된다.

그러다면 5개의 치킨집에서 3개의 치킨집을 고르는 경우의 수를 먼저 생각해야했다.
5C3은 5개의 치킨집중 순서와 상관없이 모든 경우의 수를 나타낸다.
5P3은 순서를 고려하기 때문에 사용하면 안된다.
그래서 경우의 수는 13Cm이 될 수 있다. 여기서 13인 이유는 M은 최대 13이다.

선택된 치킨집으로부터 모든 집들에 대해서 조사를 해야했다.
그리고 모든 집들에 대해서 조사를 할 때는 가장 가까운 치킨집이 거리로 설정되도록 해야했다.
그래서 아래와 같은 코드가 나왔다.

import sys
from itertools import combinations

N, M = map(int, sys.stdin.readline().split())
array = []
for i in range(N):
    array.append(list(map(int, sys.stdin.readline().split())))
houses = []
chickenStores = []

# 집과 치킨집 좌표 튜플 형태로 저장
for i in range(N):
    for j in range(N):
        if array[i][j] == 1:
            houses.append((i, j))
        elif array[i][j] == 2:
            chickenStores.append((i, j))

# 순서가 상관 없으므로 combination으로 경우의 수 나열
totalCaseChickenStores = combinations(chickenStores, M)
result = 100000  # 비교를 위해 큰 수 대입

for chicken in totalCaseChickenStores:  # combination으로 나온 모든 경우의 수의 치킨집 좌표
    distance = 0  # 거리 초기화
    for house in houses:  # 모든 집들에 대해서 하나의 치킨집 경우의 수 길이 조사
        houseChickenInterval = 100000  # 집과 치킨집 간격 초기화
        for j in range(M):  # 치킨집 M개에 대해서 길이를 측정하기 위한 for문
            houseChickenInterval = min(houseChickenInterval, abs(house[0] - chicken[j][0]) + abs(house[1] - chicken[j][1]))  # 치킨집들 중에서 가장 집과 가까운 치킨집 거리 계산
        distance += houseChickenInterval  # 집과 가장 가까운 치킨집 거리 추가
    result = min(result, distance)  # 치킨집에 대해서 모두 집과 가장 가까운 거리들이 더해짐

print(result)