[백준] 15686 치킨배달 (파이썬)

전형적인 백트래킹 문제인데 처음 풀때 거리 계산을 굳이 bfs를 이용해서 풀려고 해서 시간을 많이 잡아 먹었다.
폐업하지 않는 치킨집을 선별할때 검색해서 나오는 많은 해답들은 조합을 이용해서 후보를 선정했다.
이러한 방법을 생각하지 못했는데 편한 방법이긴 한 것 같다.

import sys
input = sys.stdin.readline

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

home, chick = [], []
for i in range(n):
  for j in range(n):
    if board[i][j] == 1:
      home.append((i,j))
    elif board[i][j] == 2:
      chick.append((i,j))
candidate = set([])
ans = sys.maxsize

def choose(res, idx):
  global ans, candidate

  if res == m:
    tmp = 0
    for i in range(len(home)):
      x1, y1 = home[i]
      cnt = sys.maxsize
      for j in candidate:
        x2, y2 = j
        dis = abs(x1-x2) + abs(y1-y2)
        if dis < cnt:
          cnt = dis
      tmp += cnt
    if tmp < ans:
      ans = tmp
    return 0

  for i in range(idx, len(chick)):
    candidate.add(chick[i])
    choose(res+1, i+1)
    candidate.remove(chick[i])

choose(0, 0)
print(ans)