조합을 먼저 구하고 BFS를 생각함.
결과는 시간초과인데, 이유는 find_C에서 일단 시간이 걸리는게
deep copy를 사용함. 2500연산에 깊이가 13Ck로 13*12*11정도의 깊이로 1700정도로 들어감
조합의 수 최대 1700가량 * 2500BFS >>> 3700만정도라 원래라면 성능이 나와줘야하지만
파이썬이기도 하고 아마 인풋에서 대신 시간을 쓰는것까지 치면 시간이 초과되는 것으로 예상
챌린징 포인트 :
1. 사실 벽이 뚫여있으면 BFS가 필요가 없다는 사실을 깨달았어야함
2. 조합을 구하는 함수는 아래와 같이 계수정렬과 유사한 좀 더 빠른 방법으로 구할 수 있음
import copy
import sys
from collections import deque
arr=[]
n, m = map(int,sys.stdin.readline().strip().split())
origin = []
for _ in range(n):
origin.append(list(map(int,sys.stdin.readline().strip().split())))
home = []
for i in range(n):
for j in range(n):
if origin[i][j] == 0:
continue
if origin[i][j] == 2:
arr.append((i,j))
if origin[i][j] == 1:
home.append((i,j))
combi = []
check = [[0]*n for y in range(n)]
def find_C(arr,index,c):
if c == m:
combi.append([])
for y in range(n):
for x in range(n):
if check[y][x] == 1:
combi[-1].append((y,x))
return True
if index >= len(arr):
return False #index 넘는 경우
for i in range(index, len(arr)):
check[arr[i][0]][arr[i][1]] = 1
find_C(arr,i+1,c+1)
check[arr[i][0]][arr[i][1]] = 0
return False
find_C(arr,0,0)
def cal(com):
ssum = 0
for h in home:
m = 999999999
for c in com:
temp = abs(h[0]-c[0])+abs(h[1]-c[1])
if temp < m:
m = temp
ssum+=m
return ssum
mmin = 999999999
for c in combi:
temp = cal(c)
if temp < mmin:
mmin = temp
print(mmin)