15686번 - 치킨 배달

문제

15686번: 치킨 배달 (acmicpc.net)

15686번: 치킨 배달

풀이

사다리 조작 문제와 동일한 조합 문제이다. 치킨집을 최대 M개 까지 남길 수 있고, M개 이하의 가능한 조합을 짜보면서 최소가 되는 도시 치킨 거리를 갱신한다. 치킨집은 최대 13개, 가정집은 최대 2N개 까지만 존재할 수 있으므로 따로 좌표를 리스트에 넣어놓고 1차원 리스트에 대해 조합을 짜도 된다.

N,M = map(int,input().split())
board = [[0]*(N+1) for _ in range(N+1)]
chickens = []
houses = []
for i in range(N):
    for j,v in enumerate(map(int,input().split())):
        board[i+1][j+1] = v
        if v == 1:
            houses.append((i+1,j+1))
        elif v == 2:
            chickens.append((i+1,j+1))


def get_answer(cnt,start):
    global answer
    if cnt > M:
        return
    # 치킨 거리 구하기
    if stack:
        result = 0
        for hr,hc in houses:
            result += min(map(lambda x : abs(x[0]-hr)+abs(x[1]-hc), stack))
        answer = min(answer,result)
    # 치킨집 조합 찾기
    for i in range(start,len(chickens)):
        stack.append(chickens[i])
        get_answer(cnt+1,i+1)
        stack.pop()


answer = int(1e9)
stack = []
get_answer(0,0)
print(answer)