[알고리즘] 치킨배달

[문제] 치킨배달
https://www.acmicpc.net/problem/15686

문제해결 hint

1)완전 탐색 문제로 파이썬 조합인 combinations을 사용하여 m개의 조합을 구한다.
2)치킨거리를 모두 계산하고 최소값을 구해 출력한다.

from itertools import combinations

n, m = 5, 3
chicken, house = [], []


for r in range(n):
    data = list(map(int, input().split()))
    for c in range(n):
        if data[c] == 1:
            house.append(r, c)
        if data[c] == 2:
            chicken.append(r, c)

# 모든 치킨집 중에서 m개의 치킨집을 뽑는 조합 계산
candidates = list(combinations(chicken, m))


# 치킨 거리의 합을 계산하는 함수
def get_sum(candidate):
    result = 0
    # 모든 집에 대하여
    for hx, hy in house:
        temp = 1e9
        for cx, cy in candidate:
            temp = min(temp, abs(hx - cx) + abs(hy - cy))
            # 가장 가까운 치킨집까지의 거리를 더하기
        result += temp
    return result


# 치킨거리의 합의 최소를 찾아 출력
result = 1e9
for candidate in candidates:
    result = min(result, get_sum(candidate))

print(result)