백준 1520번: 내리막길

문제 링크 : https://www.acmicpc.net/problem/1520

1520번: 내리막 길

 

 문제 설명 

 

1. N x M 배열에 10000이하의 자연수가 채워져 입력.

2. (0,0) 에서 (N-1,M-1) 까지 이동하는데 이동할 때 수가 높은곳에서 낮은곳으로만 이동.

3. 이동할 수있는 경우의 수 출력.

 

 알고리즘 

 

1. DP 와 DFS 를 같이 이용한문제 (개인적으로 상당히 좋은문제라고 생각) 

2. DFS 알고리즘은 수가 높은곳에서 낮은곳으로 이동할 수있게 짜줌.

3. ★이미 방문한 곳은 경우의 수를 DP배열에  저장해 시간 단축 (Point)★

 

 

 

 

 코드 

 

#include <iostream>
using namespace std;
int arr[501][501];
int dp[501][501];
int visited[501][501];
int m, n;
int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };
 
int dfs(int y, int x) {
 
    if (y == n && x == m) {
        // 오른쪽 끝에 도착하면 1 return
        return 1; 
    }
    if (visited[y][x]) //이미 방문한 곳이라면 dp[y][x] reutrn.
        return dp[y][x];
 
    for (int i = 0; i < 4; i++) {
        int next_y = y + dy[i];
        int next_x = x + dx[i];
 
        if (next_y > 0 && next_y <= n && next_x > 0 && next_x <= m)
            if (arr[y][x] > arr[next_y][next_x]){
                dp[y][x] += dfs(next_y, next_x);
                visited[y][x] = 1;
            }
 
    }
    return dp[y][x];
}
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> arr[i][j];
 
 
    cout << dfs(1, 1) << '\n';
}