🐹 치킨 배달

1. 문제 링크

15686번: 사다리 타기

2. 코드

Python3 31120KB 356ms

N, M = map(int, input().split())
city = []
chicken = []
home = []
for i in range(N):
    city.append(list(map(int, input().split())))

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

from itertools import combinations

def chicken_distance(c):
    total_distance = 0
    for h in home:
        hx, hy = h
        min_d = 2 * N
        for t in c:
            cx, cy = t
            d = abs(cx - hx) + abs(cy - hy)
            min_d = min(min_d, d)
        total_distance += min_d
    return total_distance

result = int(1e9)
for c in combinations(chicken, M):
    distance = chicken_distance(c)
    result = min(result, distance)

print(result)

3. 해설

조합으로 M개의 치킨집 위치를 선택한 후 각 집마다 가장 가까운 치킨 거리를 찾는다.

각 경우별 도시의 치킨거리를 구한 후 그 중 최소인 경우의 치킨거리를 출력한다.