[Python] 15686번 치킨 배달

✏️ 문제

 

문제 파악

빈 칸 중 m에 치킨집을 세울 수 있으므로 combinations을 사용해야 한다.

for .. in combinations(가능한 위치 배열, 개수)

 

그리고 치킨 거리의 최솟값이 필요하므로 min을 사용해 코드를 짰다.

 

 

알고리즘

• 구현
• 브루트포스 알고리즘
• 백트래킹

 

코드

import sys
from itertools import combinations
input = sys.stdin.readline

n, m = map(int, input().split())
graph = list(list(map(int, input().split())) for _ in range(n))
result = 999999
house = []     
chickens = []     

for i in range(n):
  for j in range(n):
    if graph[i][j] == 1:
      house.append([i, j])
    elif graph[i][j] == 2:
      chickens.append([i, j])

for chicken in combinations(chickens, m):  
  temp = 0 
  for h in house: 
    chicken_len = 999  
    for j in range(m):
      chicken_len = min(chicken_len, abs(h[0] - chicken[j][0]) + abs(h[1] - chicken[j][1]))
    temp += chicken_len
  result = min(result, temp)

print(result)