[백트래킹] 방향에 맞춰 최대로 움직이기

문제링크

https://www.codetree.ai/missions/2/problems/max-movements-with-direction?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 4가지 ~ 8가지 방향으로 움직일 수 있는 백트래킹 유형
• 정해진 방향으로 1칸씩이 아니라 방향에 존재하는 모든 칸으로 이동 가능
  • nr = cr + cur_dir[0] * val
  • val이 이동할 수 있는 거리를 의미함.
• 최대 이동할 수 있는 칸의 개수가 필요하다. 따라서 back 돌 때마다 ans를 갱신한다.
• nr, nc는 '='로 정의가 되어있고 계속 이동이 불가능할 때까지 새롭게 갱신된다. 따라서 nr, nc는 우리가 흔히 하는 원상태 복귀를 할 필요는 없지만 step의 경우 넣고 다시 빼주는 원상복귀가 필요하다. 

2. 코드(Python)

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
dir_board = [list(map(int, input().split())) for _ in range(n)]


dir_list = [(), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
cr, cc = map(int, input().split())
cr -= 1
cc -= 1


def in_range(r, c):
    return 0 <= r < n and 0 <= c < n


def can_move(cr, cc, nr, nc):
    return board[nr][nc] > board[cr][cc]

ans = 0
step = []
def dfs(cr, cc):
    global ans
    ans = max(ans, len(step))
    
    cur_dir = dir_list[dir_board[cr][cc]]
    for val in range(1, n + 1):
        nr = cr + cur_dir[0] * val
        nc = cc + cur_dir[1] * val
        if in_range(nr, nc) and can_move(cr, cc, nr, nc):
            step.append(board[nr][nc])
            dfs(nr, nc)
            step.pop()

dfs(cr, cc)
print(ans)