[이코테 Ch12-13] 치킨 배달 (구현)

👩🏻‍💻문제설명

[이코테 Ch12-13] 치킨 배달 (구현)

✍️Idea Sketch

문제 요약

치킨거리 : 집과 가장 가까운 치킨집과의 거리
도시의 치킨거리 : 치킨거리의 합

치킨집 m개만 남겨야 함
만들 수 있는 가장 작은 '도시의 치킨거리'는?

시간복잡도

참고사이트
이 문제는 n * n의 모든 그래프 영역을 탐색 할 필요가 없다. 집과 치킨집만 탐색하면 된다. 집은 2N개, 즉 최대 100개이며, 치킨집 M은 최대 13이다. 이는 시간 초과를 암시하는 연산횟수 1억과는 거리가 멀다. 따라서 브루트포스 알고리즘(완전 탐색)을 시도해봄직 하다.

그리고 치킨집 최대 13개 중에서 M개를 고르는 조합의 최대 경우의 수는 100,000에 가깝다. (M이 중간값 6, 7일 경우 100,000에 가깝다. )

알고리즘 : 구현, 브루트포스 (완전 탐색)

1. 치킨집 M개의 조합 구하기
2. 모든 조합에 대한 도시의 치킨거리 구하기

✍️내 소스코드

0. 빈칸, 치킨집, 집 구분하기
1. 치킨집 M개의 조합 구하기 (combinations 라이브러리 사용)
2. 모든 조합에 대한 도시의 치킨거리 구하기
   • 치킨 거리 cl : 집과 가장 가까운 치킨집과의 거리이다. 따라서 집으로부터 치킨집 사이의 거리를 모두 구한 후, 가장 작은 값을 저장한다.
   • 도시의 치킨 거리 ccl : 치킨 거리의 합이다. 치킨 거리를 구할 때마다 누적하여 더한다.
   • 모든 조합에 대한 도시의 치킨거리를 구하고, 이 중 가장 작은 값을 print한다.

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


  def get_city_chicken_len(chicken):
    ccl = 0
    for x, y in houses:
      cl = float('inf')
      for i, j in chicken:
        cl = min(cl, abs(x - i) + abs(y - j))

      ccl += cl
    return ccl


  n, m = map(int, si().split())
  houses = []
  chickens = []

  for i in range(n):
    line = si().split()
    for j in range(n):
      if line[j] == '1':
        houses.append([i, j])
      elif line[j] == '2':
        chickens.append([i, j])

  res = float('inf')
  for chicken in list(combinations(chickens, m)):
    res = min(res, get_city_chicken_len(chicken))

  print(res)