[Python][백준] 15686번 치킨 배달

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

공부 날짜 : 2022.09.13
정답 참조 여부 : X

치킨 매장을 원하는 개수만큼 남기고자 할때 남아있는 치킨 매장이 각 집으로 부터의 거리가 최소가 되는 방법을 구하는 문제

---

치킨 매장과 집의 위치를 리스트 형태로 저장하고 치킨 매장을 원하는 개수만큼 남겼을때 조합을 구한뒤 각각의 경우의 치킨 거리를 구해서 최소값을 갱신시켜 주면 된다.

소스코드

import sys
input = sys.stdin.readline

n,m = map(int,input().split())

chicken_house = []
house = []

#데이터 입력받기
for i in range(n):
    a = list(map(int,input().split()))
    for j in range(n):
        if a[j] == 1:
            house.append([i,j])
        elif a[j] == 2:
            chicken_house.append([i,j])
           
    
    
distance = int(10e9)


#남길 치킨매장의 조합을 구하는 dfs함수
def dfs(depth,new_chicken,start):
    global distance
    
    #남은 치킨매장이 조건에 맞으면 치킨거리 구한 후 거리 갱신
    if depth == m:
        distance = min(distance,check_dis(new_chicken))
        return
    
    
    for i in range(start,len(chicken_house)):
        new_chicken.append([chicken_house[i][0],chicken_house[i][1]])
        dfs(depth+1, new_chicken, i+1)
        new_chicken.remove([chicken_house[i][0],chicken_house[i][1]])
    
    
#치킨 거리를 반환하는 함수    
def check_dis(chicken):
    distance = 0
    
    for x,y in house:
        this_house_dis = int(10e9)
        for chicken_x, chicken_y in chicken:
            temp = abs(chicken_x - x) + abs(chicken_y - y)
            this_house_dis = min(this_house_dis, temp)
        distance += this_house_dis
    
    return distance    




dfs(0,[],0)
print(distance)