[알고리즘] 등산로 조성

포인트

• 재귀하고 적절한 백 트랙킹을 통해서 길을 뚫어나가는 문제입니다. 
• 재귀 설정을 잘 해주시는 게 중요합니다. 

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

python

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


def go(x: int, y: int, permit: int, length: int) -> None:
	"""
	값을 찾기 위해 돌아다니는 함수
	:param x: int
	:param y: int
	:param permit: int
	:param length: int
	:return:
	"""
	global result
	if permit < 0:
		return
	
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		
		if not (0 <= nx < n and 0 <= ny < n):
			continue
		
		if data[nx][ny] < data[x][y] and visited[nx][ny] == 0:
			visited[x][y] = 1
			go(nx, ny, permit, length + 1)
			visited[x][y] = 0
		elif data[nx][ny] - k < data[x][y] and visited[nx][ny] == 0:
			temp = data[nx][ny]
			# 임시로 데이터를 저장하는 변수
			data[nx][ny] = data[x][y] - 1
			visited[x][y] = 1
			go(nx, ny, permit - 1, length + 1)
			visited[x][y] = 0
			data[nx][ny] = temp
	
	result = max(length, result)


for test in range(1, int(input()) + 1):
	n, k = map(int, input().split())
	data = [list(map(int, input().split())) for _ in range(n)]
	highest = max(map(max, data))
	
	# 제일 큰 봉우리를 찾는다
	result = 0
	for row in range(n):
		for col in range(n):
			if data[row][col] == highest:
				visited = [[0 for _ in range(n)] for _ in range(n)]
				go(row, col, 1, 1)
	
	print('#{} {}'.format(test, result))