[알고리즘] 프로세서 연결하기

포인트

• 혼란한 문제입니다. 밑줄이 쳐져 있는 부분이 제일 중요한 포인트입니다. 최대한 많은 전원을 연결해야 하지만 그렇지 못할 경우를 고려해 줄 수 있어야 합니다.

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]


def cancel(row: int, col: int, dir: int, plus: int) -> None:
	"""
	# 시작점으로 부터 설치한 선 제거하기
	:param row:
	:param col:
	:param dir:
	:param plus:
	"""
	nx = row + dx[dir]
	ny = col + dy[dir]
	for _ in range(plus):
		data[nx][ny] = 0
		nx += dx[dir]
		ny += dy[dir]


def install(row: int, col: int, d: int):
	"""
	주어진 방향으로 설치하기 만약 브레이크를 만나면 취소
	:param row:
	:param col:
	:param d:
	:return:
	"""
	nx, ny = row, col
	dr, dc = dx[d], dy[d]
	plus = 0
	while 0 <= nx + dr < n and 0 <= ny + dc < n:
		nx += dr
		ny += dc
		if data[nx][ny]:
			break
		data[nx][ny] = 1
		plus += 1
	else:
		return plus
	# 만약 브레이크 걸리면 취소
	cancel(row, col, d, plus)
	return 0


def go(index: int, length: int) -> None:
	"""
	방향을 지정하면 얻는 함수
	:param index:
	:param length:
	"""
	global maxCores, result
	if maxCores < len(sel):
		maxCores = len(sel)
		result = 987654321
	
	if maxCores == len(sel):
		result = min(result, length)
	
	for i in range(index, len(cores)):
		for directions in range(4):
			x, y = cores[i]
			plus = install(x, y, directions)
			
			if plus !=0:
				sel.append(i)
				go(i + 1, length + plus)
				sel.pop()
				cancel(x, y, directions, plus)


for test in range(1, int(input()) + 1):
	n = int(input())
	data = [list(map(int, input().split())) for _ in range(n)]
	cores = []
	
	for row in range(n):
		for col in range(n):
			if data[row][col]:
				if row == 0 or row == n - 1 or col == 0 or col == n - 1:
					continue
				else:
					cores.append((row, col))
	
	maxCores = 0
	result = 987654321
	sel = []
	go(0, 0)
	print('#{} {}'.format(test, result))