[Python] boj no. 15686 : 치킨 배달

Problem

https://www.acmicpc.net/problem/15686

Idea

우선, 집과 치킨집의 좌표를 각각에 대한 리스트에 저장한다. 최대 M개만큼의 치킨집이 살아남을 수 있으므로 도시의 치킨 거리는 치킨집이 많이 살아남을 수록 적다.

combinations를 이용하여 치킨집 리스트에서 M개를 골라 조합 리스트를 만든 뒤, 반복문을 통해 해당 조합 리스트의 치킨집이 살아남았을 때의 도시의 치킨 거리를 계산한다. 이후, 가장 작은 도시의 치킨 거리를 구한다.

Code

import sys
from itertools import combinations

input = lambda : map(int, sys.stdin.readline().split())

N, M = input()
town = []
for _ in range(N):
    town.append(list(input()))

house = []
store = []
for i in range(N):
    for j in range(N):
        if town[i][j] == 1:
            house.append((i, j))
        elif town[i][j] == 2:
            store.append((i, j))
      
sol = sys.maxsize      
for alive in combinations(list(range(0, len(store))), M):
    dist = 0
    for h in house:
        temp = sys.maxsize
        for idx in alive:
            temp = min(temp, abs(store[idx][0] - h[0]) + abs(store[idx][1] - h[1]))

        dist += temp

    sol = min(sol, dist)
    
print(sol)

Comment