[백준_15686] 치킨배달 python

재귀함수를 이용하여,

조합을 만들어 주는 법을 미리 알고 있어야

수월하게 해결할 수 있는 문제다.

import sys

# n, m 입력
n, m = map(int, input().split())

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

# ans_list
ans_list = []

# calc()
def calc():

    # ans_list 갱신
    global ans_list

    # 전체 거리
    total_dist = 0

    for house in house_pos:
        # 집 위치 언팩킹
        hx, hy = house

        # 치킨 거리
        chicken_dist = sys.maxsize

        for chicken in alive_chicken_pos:
            
            # 치킨 위치 언팩킹
            cx, cy = chicken

            # 치킨 거리가 현재 치킨 거리보다 작다면
            if abs(hx - cx) + abs(hy - cy) < chicken_dist:
                # 치킨 거리 갱신
                chicken_dist = abs(hx - cx) + abs(hy - cy)

        # 전체 거리에 추가
        total_dist += chicken_dist
    
    # ans_list에 전체 거리 추가
    ans_list.append(total_dist)
        
# 설계
# 집들의 좌표를 담아 줄 리스트
house_pos = []

# town을 돌면서
for i in range(n):
    for j in range(n):
        
        # 집을 발견하면
        if town[i][j] == 1:
            # 좌표를 기록
            house_pos.append((i, j))

# 치킨 집들의 좌표를 담아 줄 리스트
chicken_pos = []

# town을 돌면서
for i in range(n):
    for j in range(n):
        
        # 치킨집을 발견하면
        if town[i][j] == 2:
            # 좌표를 기록
            chicken_pos.append((i, j))

# 살아남은 치킨집의 좌표를 담아 줄 리스트
alive_chicken_pos =[]

# 살아남을 치킨집 좌표의 조합 구하기
def make_comb(curr_idx, cnt):
    
    # 종료조건
    if curr_idx == len(chicken_pos):
        if cnt == m:
            # 계산
            calc()
        return
    
    # 조합 만들기
    alive_chicken_pos.append(chicken_pos[curr_idx])
    make_comb(curr_idx + 1, cnt + 1)
    alive_chicken_pos.pop()
    make_comb(curr_idx + 1, cnt)

# 조합 구하는 함수 호출
make_comb(0, 0)

# 출력
print(min(ans_list))