치킨 배달 (feat. 백준, 15686번)

치킨 배달
https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

반응형

# woohyeon.kim
from itertools import combinations

N, M = map(int, input().split())
arr = []
for _ in range(N):
  arr.append(list(map(int, input().split())))

houses = []
stores = []
for ix in range(N):
  for iy in range(N):
    if arr[ix][iy] == 1:
      houses.append([ix, iy])
    elif arr[ix][iy] == 2:
      stores.append([ix, iy])

combs = list(combinations(stores, M))
result = []
for comb in combs:
  tmp = []
  for house_x, house_y in houses:
    way = []
    for store_x, store_y in comb:
      way.append(abs(store_x - house_x) + abs(store_y - house_y))
    tmp.append(min(way))
  result.append(sum(tmp))
print(min(result))
# *&)*@*

문제의 요지는 나의 집에서 가장 가까운 치킨집 하나를 고르고

그렇게 고른 집들은 총 1의 개수만큼 존재합니다.

이때 각 집마다의 가까운 치킨집들을 더하면 이것의 하나의 순열에 대한 결과입니다.

이렇게 모든 순열을 계산했을때, 그 중에 가장 최소값입니다.