[알고리즘/백준] 15686번 : 치킨 배달(python)

처음에는 dfs와 백트래킹을 써야하는줄 알고 시간을 다 버렸다... 치킨집과 집들을 각각 리스트에 넣는다.
치킨집이 최대가 되면 치킨거리가 최소가 된다.
따라서 각 리스트를 combinations를 해서 치킨집 한개와 집 여러개의 거리를 구하는 방법으로 풀었다.

from itertools import combinations
N, M = map(int, input().split())
city = [list(map(int, input().split()))for _ in range(N)]
chicken = list()
house = list()
for i in range(N):
    for j in range(N):
        if city[i][j] == 2:
            chicken.append([i, j])
        elif city[i][j] == 1:
            house.append([i, j])
res = float('inf')
for com in combinations(chicken, M):
    tmp = 0
    for h in house:
        # t = []
        # for i in com:
        #     t.append(abs(h[0] - i[0]) + abs(h[1] - i[1]))
        # tmp += min(t)
        tmp += min([abs(h[0] - i[0]) + abs(h[1] - i[1])for i in com])
        if res <= tmp:
            break
    if tmp < res:
        res = tmp
print(res)