백준 15686. 치킨 배달

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

1. 콤비네이션 풀이

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

def calculate_distance(houses, chickens):
    total_distance = 0
    for hx, hy in houses:
        # 현재 집에서 가장 가까운 치킨집 거리
        min_distance = float('inf')
        for cx, cy in chickens:
            min_distance = min(min_distance, abs(hx - cx) + abs(hy - cy))
        total_distance += min_distance
    return total_distance

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

houses = []  # 집의 좌표 리스트
chickens = []  # 치킨집의 좌표 리스트

# 좌표 추출
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            houses.append((i, j)) # 집의 좌표 저장
        elif arr[i][j] == 2:
            chickens.append((i, j)) # 치킨집 좌표 저장

# 치킨집 조합 생성 및 최소 거리 계산
ans = float('inf')
for chicken_comb in combinations(chickens, m): # 치킨집 중 m개를 뽑는 조합
    ans = min(ans, calculate_distance(houses, chicken_comb))

print(ans)

2. 백트래킹 풀이

import sys
input = sys.stdin.readline

def calculate_distance(houses, selected_chickens):
    total_distance = 0
    for hx, hy in houses:
        min_distance = float('inf')
        for cx, cy in selected_chickens:
            min_distance = min(min_distance, abs(hx - cx) + abs(hy - cy))
        total_distance += min_distance
    return total_distance

def backtrack(start, depth):
    global min_distance
    # 치킨집을 M개 선택했으면 거리 계산
    if depth == m:
        distance = calculate_distance(houses, selected_chickens)
        min_distance = min(min_distance, distance)
        return

    # 치킨집 선택을 백트래킹으로 탐색
    for i in range(start, len(chickens)):
        selected_chickens.append(chickens[i])  # 치킨집 선택
        backtrack(i + 1, depth + 1)            # 다음 선택 진행
        selected_chickens.pop()                # 선택 해제 (백트래킹)

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

houses = []  # 집의 좌표 리스트
chickens = []  # 치킨집의 좌표 리스트

# 좌표 추출
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            houses.append((i, j))
        elif arr[i][j] == 2:
            chickens.append((i, j))

min_distance = float('inf')
selected_chickens = []  # 현재 선택된 치킨집

# 백트래킹 시작
backtrack(0, 0)

print(min_distance)