[백준/Python] #15686: 치킨 배달

문제

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

풀이

1. 모든 치킨 집 중에서 M개를 고름.

2. M개를 고른 case마다 치킨 거리를 계산.

3. 최소 거리를 갱신

4. 위 과정을 백트래킹으로 완전 탐색하며 답을 구함.

 

 

input = __import__('sys').stdin.readline
n, m = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(n)]

h = []
c = []

for i in range(n):
    for j in range(n):
        if li[i][j] == 1:
            h.append((i, j))
        elif li[i][j] == 2:
            c.append((i, j))

min_total = float('inf')
selected = []

def get_chicken_dist(selected_c):
    total = 0
    for hx, hy in h:
        min_dist = float('inf')
        for cx, cy in selected_c:
            dist = abs(hx - cx) + abs(hy - cy)
            min_dist = min(min_dist, dist)
        total += min_dist
    return total

def backtrack(start, depth):
    global min_total
    if depth == m:
        dist = get_chicken_dist(selected)
        min_total = min(min_total, dist)
        return
    for i in range(start, len(c)):
        selected.append(c[i])
        backtrack(i + 1, depth + 1)
        selected.pop()

backtrack(0, 0)
print(min_total)