🦊 치킨 배달

1. 문제 링크

15686번: 치킨 배달

2. 코드

from itertools import combinations

N, M = map(int, input().split())
CHICKEN = []
HOUSE = []
MAP = []
for i in range(N):
    line = list(map(int, input().split()))
    for j in range(N):
        if line[j] == 1:
            HOUSE.append([j, i])
        elif line[j] == 2:
            CHICKEN.append([j, i])
    MAP.append(line)
    
min_chicken_distance = 10000000
for pick in combinations(CHICKEN, r = M):
    sum = 0
    for x2, y2 in HOUSE:
        chicken_distance = 100000
        for x1, y1 in pick:
            chicken_distance = min(chicken_distance, abs(x2 - x1) + abs(y2 - y1))
        sum += chicken_distance

    min_chicken_distance = min(min_chicken_distance, sum)

print(min_chicken_distance)

Python3 31120kb 608ms

3. 해설

• 해설

  치킨집 좌표 중 M 개를 pick 하고 각 집에서 이곳들 까지의 최소 거리를 구함

  최소거리를 모두 더한 것 중 최소를 만드는 것이 정답