15686-치킨배달(파이썬)

1. 배열을 입력받고 치킨집의 위치와 집의 위치를 각각 chick , house 배열에 저장한다.

2.itertools의 combination을 활용하여 치킨집 n 개 중 r개를 고르는 nCr 을 활용하여 치킨집의 경우의 수를 반복문을 활용하여 각각 arr에 할당하여 반복문을 진행합니다

3. 변수설명

min_dist는 최종적으로 도출될 정답입니다. tot_temp와 비교해서 가장 적은 값이 min_dist가 됩니다.

tot_temp는 각 치킨집 Combination에서 도출된 거리의 총합입니다. temp의 값이 누적되어 tot_temp가 됩니다.

temp는 각 집과 치킨집사이의 거리의 최소값입니다. dist_temp와 비교하여 가장 작은 값이 temp에 저장됩니다.

dist_temp는 치킨집과 집의 거리를 저장하는 변수입니다. 가장 적은 값이 temp에 저장됩니다.

 

4.풀이 설명

모든 경우의 수를 탐색합니다

치킨집의 Combination별 각 집에서 치킨집까지의 거리의 최솟값을 계산한후

최솟값들을 모두 더해 Combination별 치킨집 거리의 최솟값을 도출해낸 후

그중 가장 작은 값을 정답으로 도출하게 됩니다.

import sys
from itertools import combinations
#sys.stdin = open("/Users/positive/Desktop/무제 폴더/Algorithm/230102/15686in.txt","r")
input = sys.stdin.readline

MAP=[]
chick = []
house = []
N,M = map(int,input().split())
dist = [[0 for _ in range(N)]for _ in range(N)]
for _ in range(N):
  MAP.append(list(map(int,input().split())))


for i in range(N):
  for j in range(N):
    if MAP[i][j]==2:
      chick.append([i,j])
    if MAP[i][j]==1:
      house.append([i,j])

min_dist = 99999999999

for arr in list(combinations(chick, M)):
  tot_temp = 0
  for h in house:
    temp = 999999
    for c in arr:
      dist_temp = abs(h[0]-c[0])+abs(h[1]-c[1])
      if dist_temp <temp :
        temp = dist_temp
    tot_temp += temp
  if tot_temp < min_dist:
    min_dist = tot_temp

print(min_dist)