[BOJ] 1520. 내리막길

*dfs와 dp를 이용하여 풀이

*도착 지점(m-1, n-1)부터 시작해서 (0,0)에 도착하면 1을 리턴하여 갈 수 있는 경로임을 저장한다. 

*만약, 이미 한 번 지나온 곳을 다시 가게 되면 중복 탐색을 할 필요가 없기 때문에 저장된 값을 리턴해준다. 

*모두 탐색했을 때 dp[m-1][n-1]에 저장된 값이 정답이다. 

*길을 중복 탐색하지 않아야 TLE를 피할 수 있다. 

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <vector> #include <algorithm> using namespace std;   int m, n, ans = 0; int map[501][501]; int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }; int dp[501][501]; bool chk[501][501]; //이 길을 한 번 거쳤는지 아닌지 판단하는 용도 (거쳤는데 DP[][]가 0이면 끝까지 가는 길이 없다는 뜻이다.) int dfs(int x, int y, int limit) {     if (!x && !y) {         return 1;     }     if (dp[x][y] != -1) return dp[x][y];       dp[x][y] = 0;     for (int i = 0; i < 4; i++) {         int nx = x + dx[i];         int ny = y + dy[i];           if (nx < 0 || nx >= m || ny < 0 || ny >= n ) continue;           if (map[nx][ny] > limit) {               //아직 안 가본 곳이라면 -> 새로운 경로             //가봤던 곳을 또 간다면 -> 이미 가본 경로일 수도 있고 가봐서 안된 경로일 수도 있다             dp[x][y] += dfs(nx, ny, map[nx][ny]);         }     }     return dp[x][y]; } int main() {       scanf("%d %d", &m, &n);       for (int i = 0; i < m; i++) {         for (int j = 0; j < n; j++) {             scanf("%d", &map[i][j]);             dp[i][j] = -1; //아직 가지 않은 곳을 표현         }     }           printf("%d\n", dfs(m - 1, n - 1, map[m - 1][n - 1]));       /*for (int i = 0; i < m; i++) {         for (int j = 0; j < n; j++) {             printf("%d ", dp[i][j]);         }         printf("\n");     }     printf("%d\n",dp[m-1][n-1]);*/       return 0; }