이해

• N x N 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다.

• “치킨 거리”는 집과 가장 가까운 치킨집 사이의 거리이고, 각각의 집은 치킨 거리를 가지고 있다. “도시의 치킨 거리”는 모든 집의 치킨 거리의 합니다.

• 임의의 두 칸 (x1, y1)과 (x2, y2) 사이의 거리는 |x1 - x2| + |y1 - y2|로 구한다.
• 도시의 치킨 거리가 가장 작게 되도록 도시에 있는 치킨집 중에서 최대 M개를 골라 도시의 치킨 거리의 최솟값을 출력하라.

계획

• 치킨집이 M개 이상 있을 경우에는 치킨집 M개를 선택해야(치킨집을 최대한 많이 선택) 치킨 거리를 구할 때 최대한 작은 값으로 치킨 거리를 선택할 수 있게 되어 도시의 치킨 거리의 최솟값을 구할 수 있게 된다.
• 집 위치가 담긴 배열과 치킨집 위치가 담긴 배열을 선언해준다.
• python의 combinations 모듈을 사용하여 치킨집을 M개 선택하는 모든 조합을 구해준다. 만약 치킨집이 M개 미만인 경우 주어진 치킨집을 모두 선택한다.
• 치킨집이 선택된 모든 조합을 탐색하며 모든 집에 대해 치킨 거리를 구해주고 다 더해주어 도시의 치킨 거리를 구해준다.

실행

from itertools import combinations

INF = int(1e9)

n, m = map(int, input().split())
people = []
chicken = []
for i in range(n):
    temp = list(map(int, input().split()))
    for j in range(n):
        if temp[j] == 1:
            people.append((i, j))
        elif temp[j] == 2:
            chicken.append((i, j))

combs = combinations(chicken, m) if len(chicken) >= m else chicken
result = INF
for comb in combs:
    chicken_d = 0
    for pos in people:
        dis = INF
        for x, y in comb:
            dis = min(dis, abs(pos[0]-x) + abs(pos[1]-y))
        
        chicken_d += dis
    result = min(result, chicken_d)

print(result)

개선

• 치킨집의 개수는 M보다 크거나 같다고 나와 있기 때문에 치킨집 개수를 고려하지 않고 치킨집을 M개 선택하는 조합을 구하면 되겠다.

from itertools import combinations

INF = int(1e9)

n, m = map(int, input().split())
people = []
chicken = []
for i in range(n):
    temp = list(map(int, input().split()))
    for j in range(n):
        if temp[j] == 1:
            people.append((i, j))
        elif temp[j] == 2:
            chicken.append((i, j))

result = INF
for comb in combinations(chicken, m):
    chicken_d = 0
    for pos in people:
        dis = INF
        for x, y in comb:
            dis = min(dis, abs(pos[0]-x) + abs(pos[1]-y))
        
        chicken_d += dis
    result = min(result, chicken_d)

print(result)

회고

• 치킨집 개수가 M개 미만인 경우에서도 combinations 모듈을 사용하여 구할 수 있는지 확인해보니까 빈 배열로 반환되었다.

arr = [1,2,3,4,5]
M = 7
print(list(combinations(arr, M))) # [] 

• 근데 문제 조건에서 치킨집의 개수는 M보다 크거나 같다고 나와 있었다.
• 조건을 제대로 살펴보지 않고 구현하여 실수할 뻔 했다. 조건을 잘 살펴보고 문제를 풀어야 겠다.