[Python] 치킨배달

문제

• 크기가 N x N인 도시가 있습니다.
• 도시는 1 x 1 크기의 칸으로 나누어져 있습니다.
• 도시의 각 칸은 빈칸, 치킨집, 집 중 하나입니다.
• 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미합니다.
• r과 c는 1부터 시작합니다.
• 이 도시에 사는 사람들은 치킨을 매우 좋아합니다. 따라서 사람들은 "치킨 거리"라는 말을 주로 사용합니다.
• 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리입니다.
• 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있습니다.
• 도시의 치킨 거리는 모든 집의 치킨 거리의 합입니다.
• 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2| 로 구합니다.
• 0은 빈 칸, 1은 집, 2는 치킨집입니다.
• (2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7입니다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2입니다.
• (5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1입니다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1입니다.
• 이 도시에 있는 치킨집은 모두 같은 프랜차이즈입니다.
• 프랜차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 합니다.
• 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아냈습니다.
• 도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 합니다.
• 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하세요.

입력

• 첫째 줄에 N(2 <= N <= 50)과 M(1 <= M <= 13)이 주어집니다.
• 둘째 줄부터 N개의 줄에는 도시의 정보가 주어집니다.
• 도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈칸, 1은 집, 2는 치킨집을 의미합니다.
• 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재합니다.
• 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같습니다.

출력

• 첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력합니다.

입력 예시

5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

출력 예시

5

문제 풀이

• m개의 치킨 집을 뽑기 위해 combination사용
• 조합 중 뽑힌 치킨 집들과 각 집의 최소 거리 구하여 최소 치킨 거리 구하기 (getsum 함수로 구현)
• 최소 치킨 거리가 나오는 조합을 찾아 그 값 출력

코드

from itertools import combinations
n, m = map(int,input().split())
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))
        elif data[c] == 2:
            chicken.append((r,c))

# 모든 치킨집에서 m개 뽑는 조합 계산
candidates = list(combinations(chicken,m))
# 치킨거리 합 구하는 함수
def getsum(candidates):
    result = 0
    for hy, hx in house:
        temp = 1e9
        for cy, cx in candidates:
            temp = min(temp,abs(hy - cy) + abs(hx - cx))
        result += temp
    return result
result = 1e9

# 최소 치킨거리 구하기
for candidate in candidates:
    result = min(result,getsum(candidate))
print(result)