boj 15686 치킨배달 (골드5)

문제

boj 15686 치킨배달

내 풀이

import sys
from itertools import combinations

input = sys.stdin.readline

n,m = map(int,input().split())

back = [list(map(int,input().split())) for _ in range(n)]

chicken = []
answer = 9999999999

for i in range(n):
  for j in range(n):
    if back[i][j] == 2:
      chicken.append((i,j))


def dist(a,b):
  return (abs (a[0] - b[0]) + abs(a[1]-b[1]))

def minDist(a,chicList2):
  answer = 99999999999
  for b in chicList2:
    answer = min(dist(a,b),answer)

  return answer

def minCheck(chicList):
  summ = 0
  for i in range(n):
    for j in range(n):
      if back[i][j] == 1:
        summ += minDist((i,j),chicList)

    if answer < summ:
      return answer

  return summ
        
for chic in combinations(chicken,m):
  answer = min(minCheck(chic),answer)

print(answer)

공부한것

조합 모듈

from itertools import combinations

a = list(combination(chicken,m))
for comb in combination(chicken,m):

이런식으로 쓸 수 있다

배열을 만들어서 불러오지말고 그냥 iter로 바로 불러다 쓰면 시간복잡도를 조금 더 줄일수 있다.

자매품으로

from itertools import permutations

for i in permutations([1,2,3,4], 2)
-> (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)

from itertools import product

for i in product([1,2,3], 'ab')
-> (1, 'a') (1, 'b') (2, 'a') (2, 'b') (3, 'a') (3, 'b')