[백준] 15686번: 치킨 배달 (python)

www.acmicpc.net/problem/15686

15686번: 치킨 배달

import sys
import itertools
    
def find_location(city, N):
    
    home = []
    chicken = []
    
    for r in range(N):
        for c in range(N):
            if city[r][c] == 1:
                home.append([r,c])
            elif city[r][c] == 2:
                chicken.append([r,c])
                
    return home, chicken
                
def cal_distance(home, chicken, n):
    
    home_distance = []
    
    for h in home:
        tmp = 2*n
        for c in chicken:
            tmp_n = abs(h[0]-c[0]) + abs(h[1]-c[1])
            if tmp_n < tmp:
                tmp = tmp_n
        home_distance.append(tmp)
        
    city_distance = sum(home_distance)
    
    return city_distance

def sel_chicken(m, chicken):
    
    possible_chicken = []
    
    for get in range(1,m+1):
        possible_chicken = possible_chicken + list(itertools.combinations(chicken,get))
        
    return possible_chicken

if __name__ == '__main__':

    N, M = map(int, input().split())
    city = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]

    home, chicken = find_location(city, N)
    possible_chicken = sel_chicken(M, chicken)

    possible_dist = []

    for c in possible_chicken:
        possible_dist.append(cal_distance(home, c, N))
        
    print(min(possible_dist))