[골드5] 15686번 : 치킨 배달

🛠 문제

https://www.acmicpc.net/problem/15686

👩🏻‍💻 해결 방법

조합을 사용해 모든 경우의 수를 확인해주며 최솟값을 갱신하는 방식으로 풀 수 있었다

소스 코드

from itertools import combinations

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

home = []
chicken = []
for i in range(n):
  for j in range(n):
    if arr[i][j] == 1:
      home.append((i, j))
    elif arr[i][j] == 2:
      chicken.append((i, j))

min_dis = float('inf')
for ch in combinations(chicken, m):
  sum_dis = 0
  for i in home:
    sum_dis += min([abs(i[0]-j[0])+abs(i[1]-j[1]) for j in ch])
    if min_dis <= sum_dis:
      break
  
  if sum_dis < min_dis:
    min_dis = sum_dis

print(min_dis)