[Python](구현, 조합) 백준 15685번 : 치킨 배달

---

<접근 방법>

1. 집과 치킨집 사이의 거리를 구해야하므로
   집(arr[i][j] == 1)과 치킨집(arr[i][j] == 2)의 좌표를 각각 loc_house, loc_chicken 리스트에 저장한다.
   

   

   예제 2의 house들의 좌표와 chicken집들의 좌표

2. distance라는 이차원 배열을 만들어서 행과 열은 각각 집과 치킨집을 나타내도록 하고 서로의 거리를 구한다.

예제 2의 distance 배열

3. 조합의 결과로 나올 수 있는 치킨집의 경우의 수를 구해
    각 집들에 있어 살아남은 치킨집들까지의 최소 거리(temp)를 total에 더한다.
4. 하나의 조합의 결과가 total이고, 우리가 구하고자 하는 정답은 answer, 즉 조합들의 결과 중 가장 최소인 값을 구하는 것
    이 목표이므로 answer = min(answer, total)로 정답을 갱신해준다.

from itertools import combinations

N, M = map(int, input().split())    # NxN 도시, M:남길 치킨집 개수
arr = [list(map(int, input().split())) for _ in range(N)]
loc_house = []      # 집들의 좌표를 담을 리스트
loc_chicken = []    # 치킨집들의 좌표를 담을 리스트
for i in range(N):
    for j in range(N):
        if arr[i][j] == 1:
            loc_house.append((i, j))
        elif arr[i][j] == 2:
            loc_chicken.append((i, j))

# 집들과 치킨집들 간의 각각의 거리를 distance라는 이차원 배열로 만들기
distance = [[0]*len(loc_chicken) for _ in range(len(loc_house))]
for i in range(len(loc_house)):
    for j in range(len(loc_chicken)):
        distance[i][j] = abs(loc_house[i][0]-loc_chicken[j][0]) + abs(loc_house[i][1]-loc_chicken[j][1])

answer = 1e9
for rest in combinations(range(len(loc_chicken)), M):
    total = 0
    for i in range(len(loc_house)):
        temp = 2*N  # 가장 멀리 떨어져 있어도 거리가 2*N을 넘지 않으므로 2*N으로 설정
        for j in rest:
            if distance[i][j] < temp:   # 가장 가까운 거리로 갱신
                temp = distance[i][j]
        total += temp   # 최종적으로 갱신된 결과를 total에 합산
    answer = min(total, answer)	# 최소 치킨 거리로 정답을 갱신
print(answer)

이해가 안되는 부분이 있으면 질문 주세요. 감사합니다.