[백준] 치킨배달(Python) - 구현 & 백트래킹

# 문제 

문제가 언뜻 보면 복잡해보이지만, 사실 M개의 치킨집을 선택하는 최적의 입지를 구하는 문제다. 여기서 최적의 입지의 기준이란 각 집으로부터 "치킨거리"의 합이 가장 작아지는 M개의 치킨집을 고르는 경우를 구하는 것 !  "치킨거리"를 구하는 공식 또한 인덱스를 기준으로 하기에 그렇게 어렵지 않다. 

 

# 입출력 

 

# Idea

 

# Code

우선 이 문제는 구현과 백트래킹으로 풀 수 있으므로, 구현으로 푸는 방법을 먼저 소개하겠다. itertools의 combination 함수를 이용하면 쉽게 구현 가능하다. 

"""
치킨 배달 
  - Combination으로 먼저 풀기
"""
from itertools import combinations

# 해당 치킨집 조합과 1들의 거리를 리턴하는 함수 
def distance(one_list, two_ele) : 
  dis = 0 
  for one_ele in one_list : 
    how_min = 99999 
    for t in two_ele : 
      # 둘 중 min 값만 저장 
      how_min = min(abs(one_ele[0] - t[0]) + abs(one_ele[1] - t[1]), how_min)
    dis += how_min
  return dis


if __name__ == '__main__':
  N, M = map(int, input().split())
  m = []     # map 
  result = 999999    # 도시의 치킨거리 최솟값 

  for _ in range(N):
    m.append(list(map(int, input().split())))

  # 1과 2 위치 적재 
  ones = [] ; twos = []
  for i in range(N):
    for j in range(N):
      if m[i][j] == 1 : 
        ones.append((i+1, j+1))   # 튜플로 적재 
      elif m[i][j] == 2 : 
        twos.append((i+1, j+1))

  chi = list(combinations(twos, M))       # 치킨집 M개 고르는 경우의 수 

  # 치킨집 조합별 반복문 
  for two_ele in chi : 
    result = min(result, distance(ones, two_ele))

  print(result)