치킨배달 파이썬 백준 16234

문제

input

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

output

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

TODO

1. n,m,city = input data 

2. home, chicken 위치구하기

3. 치킨거리구하기: sum(home[i]에서 가장 가까운 치킨집 거리)

4.
	살려줄 치킨집 리스트 ++
	if 치킨집 갯수 == m :
		result = max(result,치킨거리구하기())

CODE

n,m = map(int,input().split()) 
city = [list(map(int,input().split())) for _ in range(n)] 
home = [] 
chick = [] 
for i in range(n) : 
    for j in range(n): 
        if city[i][j] == 1 : 
            home.append((i,j))
        elif city[i][j] == 2 : 
            chick.append((i,j)) 


def dist(ch_list): 
    dist = 0
    for h in home: 
        mini = float("inf")
        for ch in ch_list : 
            mini = min(mini,abs(h[0] - ch[0]) + abs(h[1] - ch[1]))
        dist += mini 
    return dist 

def del_m(cnt, ch_list, ret,i): 
    if cnt == m :
        ret = min(ret, dist(ch_list)) 
        return ret 
    for index,c in enumerate(chick):
        if not c in ch_list and index > i: 
            ch_list.append(c)
            ret = del_m(cnt+1, ch_list, ret, index)
            del ch_list[-1]
    return ret
    

if __name__ == "__main__": 
    print(del_m(0,[],float("inf"),-1))