치킨 배달 [백준 15686] - python

import sys 
from itertools import combinations

def BOJ15686() :
  N, M = map(int, sys.stdin.readline().split())
  graph = []
  for _ in range(N) :
    graph.append(list(map(int, sys.stdin.readline().split())))

  chiken_store_list = []
  house_list = []

  for x in range(N) :
    for y in range(N) :
      if graph[x][y] == 1 :
        house_list.append([x+1, y+1])
      elif graph[x][y] == 2 :
        chiken_store_list.append([x+1, y+1])

  chiken_store_combination = list(combinations(chiken_store_list, M))
  answer = 1e9
  for chicken_store_lists in chiken_store_combination :
    temp = 0
    for house in house_list :
      temp_length = 1e9
      house_x, house_y = house
      for chicken_store in chicken_store_lists :
        chicken_x, chicken_y = chicken_store
        temp_length = min(temp_length, abs(chicken_x - house_x) + abs(chicken_y - house_y))
      temp += temp_length
    answer = min(answer, temp)
  print(answer)

BOJ15686()

 

접근방법 :

1.  문제에서 요구하는 것은 치킨집을 M개 골랐을 때 최소의 치킨거리를 구하는 것이다. 조합을 이용해야 겠다 생각이 들었다.

2. combination 모듈을 이용해 M개를 뽑는 모든 조합을 고른후

3. 뽑아낸 조합에 모든 집들간의 치킨 거리를 구해서 최솟값을 비교해 주었다

 

 

막간 상식 (중요한 내용 아님)

* 여기서 말하는 치킨 거리는 맨하탄 거리다

두점 사이의 거리를 구하는 명칭에는 우리가 흔히 아는 유클리드 거리가 있다  루트((x1-x2)의 제곱 + (y1-y2)의 제곱) 인데.

맨하탄 거리는 abs(x1-x2) + abs(y1-y2) 이다. 

여기서 말하는 맨하탄은 이름에서 짐작가능한 뉴욕의 맨하탄이 맞다. 

맨하탄은 빌딩이 굉장히 많은데 a지점에서 b지점으로 갈때의 거리를 구할때 아래 이미지와 같이 빌딩 단위로 계산한거에서 유래 되었다고 들었다.

 

 

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달