[백준 15686] 치킨 배달 (Python)

2022. 8. 23. 11:23

문제 링크 #

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

문제 해설 #

Idea #

Combinations
최대 집의 개수가 100, 최대 치킨집의 개수가 13으로 매우 적은 경우의 수를 가지고 있기 때문에,
모든 조합에 대한 완전탐색을 통해 최소 거리를 계산
초기에는 집에 대한 치킨 거리가 작은 치킨집을 우선적으로 선발해서,
폐업하지 않은 치킨집에 대한 치킨 거리의 최소 합을 계산했지만 틀림
이후 combinations 모듈을 활용한 완전탐색을 통해 통과

Time Complexity #

O(N * nCr) ~ 100,000

Data Size #

N: 2 <= int <= 50
M: 1 <= int <= 13
cell in (0, 1, 2)
count(house): 1 <= int < 2N
count(chicken): M <= int <= 13

해설 코드 #

python

from itertools import combinations
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
city = {'0':list(),'1':list(),'2':list()}
for r in range(N):
    for c,i in enumerate(input().split()):
        city[i].append((r,c))
houses, chickens = city['1'], city['2']
diff = lambda c1,c2: abs(c1[0]-c2[0])+abs(c1[1]-c2[1])

# =============== 1안 (틀림) ===============

house_cost = {chicken:0 for chicken in chickens}
chicken_cost = {house:house_cost.copy() for house in houses}

for house in houses:
    for chicken in chickens:
        cost = diff(house,chicken)
        chicken_cost[house][chicken] = cost
        house_cost[chicken] += cost

city_cost = 0
open = [chicken for chicken,cost in sorted(house_cost.items(), key=lambda x: x[1])[:M]]
for house, costs in chicken_cost.items():
    city_cost += min([cost for chicken,cost in costs.items() if chicken in open])

# =============== 2안 (통과) ===============

city_cost = sys.maxsize
for comb in combinations(chickens, M):
    cost = 0
    for house in houses:
        cost += min([diff(house,chicken) for chicken in comb])
    city_cost = min(city_cost,cost)

print(city_cost)