[baekjoon] 15686 치킨 배달 (python3)

문제

---

집-치킨집의 거리는 맨하탄 거리로 구한다. ( |x1 - y1| + |x2 - y2| )
어떤 집의 치킨 거리는 가장 가까운 치킨집과의 거리이고, 모든 집들의 치킨 거리의 합이 도시의 치킨거리이다.
이 때 도시의 치킨거리가 최소가 되도록 치킨 집을 m개 골라야한다.

접근법

---

1 <= m <= 치킨집 <= 13 이기 때문에 단순히 치킨집을 m개 골라도 최대 13 \choose 6 = 1716 가지 밖에 없다.
도시의 치킨거리를 구할 때 k개의 집에 대해 m개의 치킨집과의 거리를 비교해야하므로 O(km)
k <= 2N <= 100 이므로 combination의 경우의 수 * O(km) 을 해도 1300 * 1716 이 최대일 것
따라서 그냥 모든 경우의 수에 대해 도시의 치킨거리를 구해도 될 것 같다.

code

---

도시의 정보가 2차원 배열 형태로 주어지면 집과 치킨집의 위치를 리스트에 저장해둔다.
저장된 위치 정보를 가지고 치킨 거리를 구한다.

from itertools import combinations

n, m = map(int, input().split())
homes = []
chickens = []

for i in range(n):
    l = input().split()
    for j in range(n):
        if l[j] == '1':
            homes.append((i, j))
        elif l[j] == '2':
            chickens.append((i, j))

def get_chic_dist(h, c):
    return abs(h[0] - c[0]) + abs(h[1] - c[1])

answer = -1
for chic_case in combinations(chickens, m):
    # m개의 치킨집을 고르고 각 케이스에 대한 연산
    sum = 0
    for h in homes: # 집집 마다 치킨거리를 구한다.
        mind = -1
        for c in chic_case:
            d = get_chic_dist(h, c)
            mind = d if mind == -1 else min(mind, d)
        sum += mind

    answer = sum if answer == -1 else min(answer, sum)  

print(answer)

건전한 피드백은 언제나 환영입니다 :D