책너두 - 알고리즘 챌린지[3/20]

오늘의 문제 : 치킨배달

뭔가 더 최적화시킬 방법이 있을 거 같은데..

주어지는 값의 범위가 작아, 조합을 통해 전체 경우의 수를 구해 풀어버렸다.

혹시나 다른 분 풀이가 있을까해서 구글링도 해봤는데 다들 비슷하게 풀고 내려놓으신 것 같다.

여기서 조금만 범위가 늘어난다면 다시 풀어야 할 것 같은데 그 땐 어떻게 풀어야할지..!

import sys
from itertools import combinations
n, m = map(int, sys.stdin.readline().split())
homes = []
chickens = []

for i in range(n) :
    graph = list(map(int, sys.stdin.readline().split()))
    for j in range(len(graph)) :
        if graph[j] == 1 :
            homes.append([i, j])
        elif graph[j] == 2 :
            chickens.append([i, j])

ans = 10000
for chicken in combinations(chickens, m) :
    total_length = 0
    for home in homes :
        x, y = home
        length = 100
        for chick in chicken :
            c, r = chick
            length = min(length, abs(x - c) + abs(y - r))              
        total_length += length
    ans = min(ans, total_length)

print(ans)