[BOJ][Python]15686 풀이

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

15686번: 치킨 배달

import sys; ssr = sys.stdin.readline
INF = 2501

def get_chicken_distance(chicken_locations, house_locations):
    result = []
    for house_r, house_c in house_locations:
        chicken_distance = INF
        for chick_r, chick_c in chicken_locations:
            tmp = abs(chick_r - house_r) + abs(chick_c - house_c)
            if tmp < chicken_distance:
                chicken_distance = tmp
        result.append(chicken_distance)
    return result

def f(num, idx, selected_chickens):
    global ans
    if num == m:
        tmp = sum(get_chicken_distance(selected_chickens, houses))
        if tmp < ans:
            ans = tmp
        return
    for i in range(idx, len(chickens)):
        selected_chickens.append(chickens[i])
        f(num+1, i+1, selected_chickens)
        selected_chickens.pop()
        
n, m = map(int, ssr().split())
city = [list(map(int, ssr().split())) for _ in range(n)]
houses = []
chickens = []
dists = []
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            houses.append((i, j))
        elif city[i][j] == 2:
            chickens.append((i, j))
ans = INF
f(0, 0, [])
print(ans)

 

원래는 식을 세워서 문제를 풀어보려고 했는데 좀 쉽지 않아서 브루트포스로 노선을 틀었습니다. 입력 범위도 별로 안크니까 브루트포스를 써도 충분히 돌아가긴 하네요. 그 외에는 딱히 신경써줘야 할 부분은 없는 것 같네요.