[파이썬] [구현] 백준 15686 치킨 배달

문제

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

15686번: 치킨 배달

코드

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

n,m=map(int, input().split())
array=[list(map(int, input().split())) for _ in range(n)]

chi=[]
for i in range(n):
    for j in range(n):
        if array[i][j]==2:
            chi.append([i,j])

home=[]
for i in range(n):
    for j in range(n):
        if array[i][j]==1:
            home.append([i,j])

result=[[0]*len(chi) for _ in range(len(home))]
for i in range(len(home)):
    for j in range(len(chi)):
        a,b=home[i]
        c,d=chi[j]
        result[i][j]=abs(a-c)+abs(b-d)
temp1=0
ans=10000
com=(list(combinations(range(0,len(chi)),m)))

for k in range(len(com)):
    for i in range(len(home)):
        temp=10000
        for j in range(len(chi)):
            if j in com[k]:
                temp=min(temp, result[i][j])
        temp1+=temp
    ans=min(ans,temp1)
    temp1=0

print(ans)