[문제풀이 py] B15686 치킨배달

치킨배달 / 조합 🛒

---

  🎠. 'itertools 모듈'을 이용해 'combinations()'를 사용하여 조합을 구할 줄 알아야 한다.
  🎠. 조합을 구해 '각 경우를 돌 때', 이 for in문은 '가장 바깥에' 위치해야 한다. => '경우에 따른 결과'를 구해야 함으로
  🎠. 이전 값과 비교할 때, '이전값을 할당하는 변수'는 'for in문 바깥'에 위치해야 한다. => '(현재값과 이전값에 대한)'비교는 for in문 안에서

  import itertools
  import sys

  N, M = map(int, input().split())
  arr2d = []
  for _ in range(N):
      arr2d.append(list(map(int, input().split())))
  # print(arr2d)

  # 치킨집, 집 좌표 구하기
  chickens = []
  homes = []
  for i,row in enumerate(arr2d):
      for j,info in enumerate(row):
          if arr2d[i][j] == 2:
              coord = []
              coord.append(i)
              coord.append(j)
              chickens.append(coord)
          elif arr2d[i][j] == 1:
              coord = []
              coord.append(i)
              coord.append(j)
              homes.append(coord)

  # 치킨집 M개 만큼 조합
  res = itertools.combinations(chickens, M)
  comb = list(res)
  # print("comb:", comb)

  case_prev = sys.maxsize
  for case in comb: # 현재 경우 도시의 치킨거리 구하기
      sum = 0
      for home in homes: # 현재 집에 대해 치킨거리 구하기
          dist_prev = sys.maxsize
          for chick in case: # 현재 경우 치킨집을 돌면서
              dist = abs(home[0]-chick[0]) + abs(home[1]-chick[1])
              dist_prev = min(dist_prev, dist)
          sum += dist_prev
      # print(sum)
      case_prev = min(case_prev, sum)
  print(case_prev)

💡. 문제 접근 방법
: 도시에 치킨집 중에 M개를 고르고 나머지는 폐업시켜야 한다.
여기서 치킨집을 고르는 순서는 결과에 영향을 미치지 않음으로, 조합(combination)을 써야겠다고 생각했다.
일단,
치킨집과 집이 있는 좌표를 구해 각각의 리스트에(chickens, homes) 넣는다.
그리고, 치킨집 좌표들의 M-길이의 조합을 구한다.
그렇게 생긴 조합들의 각 경우를 돌면서, 각 경우에 대한 도시의 치킨거리를 구한다.
전의 도시의 치킨거리와 비교해 더 작은 값을 구하여, 답을 구한다.