파이썬 백준 15686번 : 치킨 배달

문제

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

 

 

🍗풀이

N,M의 범위가 작아 브루트포스로 모든 경우의 수를 고려했다.   

import sys
from itertools import combinations


N,M=map(int,sys.stdin.readline().split())
home=[]
chicken=[]
for i in range(N):
    temp=list(map(int,sys.stdin.readline().split()))
    for j in range(N):
        if temp[j]==1:
            home.append((i,j))
        if temp[j]==2:
            chicken.append((i,j))

combs=list(combinations(chicken,M)) #만들수 있는 모든 치킨집 조합 저장 

chicken_distance=[]
answer=10000


for comb in combs:
    chicken_distance = []
    for i in range(len(home)):
        distance = 10000
        for c in comb:
            result= abs(c[0]-home[i][0])+abs(c[1]-home[i][1])
            distance=min(distance,result)
        chicken_distance.append(distance)
    answer=min(answer,sum(chicken_distance))

print(answer)