[백준 15686] 치킨 배달 (Python)

👩🏻‍💻문제링크

[백준 15686] 치킨 배달 (Python)

✍️Idea Sketch

2021-08-10

1. 출력값 분석하기

• 치킨거리 : 집과 가장 가까운 치킨집 사이의 거리
• 집 (x1, y1), 치킨집 (x2, y2) 일 때, 치킨거리는 |x1-x2| + |y1-y2| 이다.
• 도시의 치킨거리 : 모든 치킨거리의 합
• 도시의 치킨거리의 최솟값은?

2. 입력값 분석하기

• 도시의 크기는 n*n 이다.
• 치킨집은 m개 빼고 다 폐업할 예정이다.
• 0은 빈칸이다.
• 1은 집이다.
• 2는 치킨집이다.

3. 로직 살펴보기

• 치킨집이 5개고, m이 2인 경우
• 치킨집 5개 중에 2개를 고르는 모든 조합을 combinations 로 구한다.
• city_length()에서 치킨거리 min_length 와 도시의 치킨거리 total을 구한다.
• 도시의 치킨거리의 최솟값 result 를 구한다.

✍️소스코드

2021-08-10 356ms 통과

import sys
from itertools import combinations

def city_length(shops):
  total = 0
  for house_x, house_y in houses:
    min_length = sys.maxsize
    for shop_x, shop_y in shops:
      length = abs(house_x - shop_x) + abs(house_y - shop_y)
      min_length = min_length if min_length < length else length
    total += min_length
  return total

if __name__ == '__main__':
  n, m = map(int, input().split())

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

  result = sys.maxsize
  for shops in list(combinations(shops, m)):
    total = city_length(shops)
    result = result if result < total else total
  print(result)