[기출/삼성전자] 백준 15686번: 치킨 배달

-문제: https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

부족했던 점: 

파이썬에서 combinations는 n개에서 m개를 선택한 모든 경우의 수를 구해준다 

치킨거리를 구할 때는 '집'을 기준으로 계산한다 

get_sum()에서 하나의 집 위치 (hx,hy)를 기준으로 각 치킨 집과의 거리를 result에 더한다

from itertools import combinations

n,m=map(int,input().split())
chicken,house=[],[]

for r in range(n):
    data=list(map(int,input().split()))
    for c in range(n):
        if data[c]==1:
            house.append((r,c))
        elif data[c]==2:
            chicken.append((r,c))
            
candidates=list(combinations(chicken,m))

def get_sum(candidate):
    result=0
    for hx,hy in house:
        temp=1e9
        for cx,cy in candidate:
            temp=min(temp,abs(hx-cx)+abs(hy-cy))
        result+=temp
    return result 
        
result=1e9
for candidate in candidates:
    result=min(result,get_sum(candidate))
    
print(result)