백준 파이썬 15686 치킨 배달

백준 링크:https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

가능한 빠르게 배달이 가능한 치킨의 집 M을 구해서 합을 구하면 되는 문제였다.

 

초반엔 BFS를 사용해서 구해야 하나? 라고 생각헀지만 너무나 비효율적이라 생각해서 그냥 위치만 저장하고

 

itertools 의 combinations를 사용해서 모든 경우의 수에 대한 합 중 가장 낮은 값을 넣었다.

 

생각해보면 엄청 간단한 문제이지만 요상하게 시간이 많이 걸린거 보니 그냥 재능이 없어보인다 ㅎ.

 

from itertools import combinations
import sys

INF = sys.maxsize

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

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

cnt = 0

h = {}
c = []
for i in range(n):
    for j in range(n):
        if s[i][j] == 1:
            h[i,j] = INF
        elif s[i][j] == 2:
            c.append([i,j])

a = list(combinations(c,m))

result = INF

for i in a:
    answer = 0
    for j in h:
        h[j] = INF

    for y in i:
        for x in h:
            h[x] = min(h[x],abs(x[0]-y[0])+abs(x[1]-y[1]))

        result = min(result,sum(h.values()))

print(result)

 

더 나은 풀이가 있을지도??