python 백준15686 치킨 배달(BOJ15686)

문제링크 : https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

처음에 문제읽다가 이게 뭐말이래..했는데

생각보다 할만했다 한방에 통과!

from itertools import combinations
import sys

input = sys.stdin.readline

#도시사이즈n , 고를 치킨집 개수m
n, m = map(int, input().split())
input_map = []
zip = []
chicken = []

#입력
for i in range(n):
  input_map.append(list(map(int, input().split())))
  for j in range(n):
    #집 좌표
    if input_map[i][j] == 1:
      zip.append((i,j))
    #치킨집 좌표
    if input_map[i][j] == 2:
      chicken.append((i,j))
      
#치킨집 m개 남기는 모든 조합
combination_chicken = list(combinations(chicken, m))

#max값
INF = int(1e9)

#치킨거리 
city_chicken_distance = INF

#치킨 조합중 하나 뽑기
for group in combination_chicken:
  #뽑힌 조합의 치킨거리 합
  chicken_distance = 0
  #집을 하나 뽑고
  for i in zip:
    a, b = i
    #뽑힌집에서 가장 가까운 치킨거리
    short_dist = INF
    
    #가장 가까운 치킨거리
    for i in group:
      x, y = i
      dist = abs(a-x) + abs(b-y)
      if(dist < short_dist):
        short_dist = dist
    #치킨거리 합산
    chicken_distance += short_dist

  # 해당 치킨집 조합이 최소 도시치킨거리라면 업데이트
  if chicken_distance < city_chicken_distance:
    city_chicken_distance = chicken_distance
#출력
print(city_chicken_distance)

그치만 속도가 좀 느리다..

다른사람들 코드보면서 참고해봐야겠다