CodeAngie

문제게임 보드 위의 숫자에 따라 동전을 이동시킬 때, 동전을 움직이는 횟수가 최대가 되도록 하는 문제이다.보드 위의 숫자는 1부터 9까지 있으며, 해당 칸에서 다음 칸으로 이동할 때 표기된 숫자만큼 한 번에 이동해야 한다.동전은 상하좌우로 이동할 수 있고, H(구멍) 칸이나 보드 바깥으로 이동되면 게임이 종료된다.풀이이 문제에서는 깊이 우선 탐색(DFS)과 메모이제이션, 백트래킹을 사용해 풀 수 있다.재귀적으로 DFS를 사용해서 동전이 이동할 수 있는 모든 경로를 탐색한다.메모이제이션 DFS 탐색을 하면서 특정 칸에 대한 경로 탐색이 끝나면, 그 칸에서 최대 이동 횟수를 계산한 상태이다.따라서 중복 탐색을 방지하기 위해, 계산된 값을 메모이제이션을 통해 저장한다.탐색 도중 이미 계산된 값( dp[x][y..