아이디어 처음에는 단순히 dfs 를 이용해서 문제를 해결하려 했으나 이 경우 시간초과가 발생하게 된다. 따라서 한 번 방문한 곳에 대한 정보를 저장하는 방식을 사용할 필요가 있어 dfs + dp 방식의 풀이를 적용했다. dp[i][j] 를 (i, j) 에서 (M - 1, N - 1) 까지 갈 수 있는 경로의 수라고 정의한다면 (i, j) 의 상/하/좌/우 좌표 중 좌표값이 (i, j) 의 값보다 더 작은 dp[x][y] 들의 합이 된다. 추가로 dp 배열은 -1 로 초기화를 해주어야 하는데 그 이유는 (i, j) 에서 (M - 1, N - 1) 까지 갈 수 있는 경로의 수가 0 개인 경우도 존재하기 때문이다. 초기값이 아닌 경우 탐색한 것으로 간주하는 방식을 취할 것인데 초기값이 0이면 경로의 수가 0인..