15686 - 시뮬

nhwang·2022년 4월 11일
0

조합을 먼저 구하고 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)
profile
42Seoul

0개의 댓글