[BOJ] 1520. 내리막길

*dfs와 dp를 이용하여 풀이

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

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

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

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

 

 

#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; }