[파이썬] 백준 15686 치킨 배달

구현은 다했는데 메모리 초과가 난다. 조합 부분에서 나는 것 같다. 함수를 사용하지 않고 아래처럼 구현하면 된다고 한다.

from collections import deque
from itertools import combinations
import sys
 
# 치킨집에서 집까지의 최솟값 구하기
 
def find(temp,h):
 
    answer =1000000
 
    for i in range(0,len(temp)):
 
        if abs(temp[i][0]-h[0]) + abs(temp[i][1]-h[1]) < answer:
            answer = abs(temp[i][0]-h[0]) + abs(temp[i][1]-h[1]) 
 
    return answer
 
def check(temp,h):
 
 
    answer = [ ] 
    temp = list(temp)
    sums = 0
 
    for i in range(0,len(h)):
        answer.append(find(temp,h[i]))
 
 
 
    return answer
 
 
 
 
 
N,M =map(int, sys.stdin.readline().split())
 
 
k = [ ]
 
 
for i in range(N):
    k.append(list(map(int, sys.stdin.readline().split())))
 
 
c = [ ]
h = [ ]
 
for i in range(0,len(k)):
    for j in range(0,len(k[i])):
        if k[i][j]==1:
            c.append([i,j])
 
        if k[i][j]==2:
            h.append([i,j])
 
 
temp = list(combinations(c,M))
 
 
# temp 별로 각 집까지의 최소를 구한 후 그 합이 최소인 경우를 answer 에 update
 
answer = [ ]
 
for i in range(0,len(temp)):
 
 
    answer.append(check(temp[i],h))
 
ans = [ ]
 
for i in answer:
    ans.append(sum(i))
 
 
print(min(ans))  
 
 
 
 
 
 
 
 
 
 
 
 

 

 

from itertools import combinations 
​
n, m = map(int, input().split())
answer = float('inf')
​
house, chicken = [], []
​
for i in range(n):
    row = list(map(int, input().split()))
    for j in range(n):
        if row[j] == 1:
            house.append((i, j))
        elif row[j] == 2:
            chicken.append((i, j))
​
​
​
​
for combi in combinations(chicken, m):
  total_distance = 0
  for r1, c1 in house:
    distance = float('inf')
    for r2, c2 in combi:
      distance = min(distance, abs(r1 - r2) + abs(c1 - c2))
      total_distance += distance
      answer = min(answer, total_distance)
​
print(answer)