15686번 치킨 배달 G5

크기가 N*N인 도시에 집과 치킨집들이 있다.

집(x1, y1)과 치킨집(x2, y2)사이의 거리( |x1-x2| + |y1-y2| )를 치킨 거리라고 하고 가장 가까운 치킨집을 기준으로 계산된다.

도시의 치킨 거리는 모든 집의 치킨 거리의 합.

집과 치킨집의 위치 정보가 주어지고 주어진 치킨집에서 m개의 치킨집만 남기고 모두 폐업시킨다고 했을 때 도시의 치킨 거리가 최소가 되는 경우를 구해야하는 문제이다.

조건 : N(2≤N≤50), M(1≤M≤13), 1≤집의 개수≤2N, 치킨집의 개수≤13

백트래킹을 사용해 m개의 치킨집을 골랐다.
그전에 미리 각 집마다 모든 치킨집에 대한 치킨 거리를 구해놓았다.
m개의 치킨집을 모두 선택했다면 각 집마다 선택된 치킨집들과의 치킨 거리 중에서 가장 가까운 치킨집을 선택하고 도시 치킨 거리에 추가했다.

그렇게 모든 경우에 대해 도시 치킨 거리를 구하고 그 중에서 가장 최소값을 답으로 출력했다.

구현할 때 조금 헷갈렸던 것 빼면 재미있는 문제였다.

from sys import stdin

def chicken_dist():
    #check를 통해 pick된 치킨집들로 치킨 거리 계산하고 result에 추가
    global check, result, house
    ans = 0
    #각 집에 대해서 선택된 치킨집 중 가장 가까운 거리를 추가
    for home in house:
        #house[home] -> 각 집과 치킨집들과의 거리
        #pick된 치킨집 중에서 제일 가까운거를 선택
        i = 0
        min_dist = float('inf')
        for h in house[home]:
            if check[i] == 1:
                min_dist = min(min_dist, house[home][h])
            i+=1
        ans+=min_dist
    result.append(ans)

def pick_chicken(k, p):
    global check, chicken
    #m개를 다 고르면 치킨거리 계산
    if k == m:
        chicken_dist()
        return
    
    for i in range(p, len(chicken)):
        if check[i] == 0:
            check[i]=1
            pick_chicken(k+1, i+1)
            check[i]=0

#치킨집 최대 13개
#각 집마다 모든 치킨집에 대한 치킨 거리를 구해놓고
#m개의 치킨집을 골랐을 때 치킨 거리를 구한다
#다 해보고 가장 작은애로 한다

n, m = map(int, stdin.readline().split())
city = [list(map(int, stdin.readline().split())) for i in range(n)]

#모든 치킨집과 집의 위치 저장
chicken = []
house = {}
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            house[(i,j)] = {}
        elif city[i][j] == 2:
            chicken.append((i,j))

for x in chicken:
    for h in house:
        house[h][x] = abs(x[0]-h[0]) + abs(x[1]-h[1])

#백트래킹을 사용해서 m개를 고르는 경우로 해결
check = [0 for i in range(len(chicken))]
result = []
pick_chicken(0, 0)

print(min(result))