구현_심화13) 치킨 배달 _ python

링크

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

15686번: 치킨 배달

코드

import itertools
N, M = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(N)]
house = []
chicken = []

for i in range(N):
    for j in range(N):
        if city[i][j] == 1:
            house.append([i+1,j+1])
        elif city[i][j] == 2:
            chicken.append([i+1,j+1])

answer = 2 * N * len(house)
for chicken_open in itertools.combinations(chicken, M):
    city_chicken_road = 0
    for h in house:
        chicken_road = 2 * N
        for c in chicken_open:
            chicken_road = min(abs(h[0] - c[0]) + abs(h[1] - c[1]), chicken_road)
        city_chicken_road += chicken_road
    answer = min(city_chicken_road, answer)
print(answer)