[백준 1890] 점프 (DFS, DP) (C/C++)

#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int map[110][110];
long long dp[110][110];
 
int dx[2] = {0, 1}; // 우하
int dy[2] = {1, 0}; // 우하 
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
long long DFS(int x, int y)
{
    if(x == N-1 && y == N-1)
    {
        return 1;
    }
    else if(map[x][y] == 0)
    {
        return 0;
    }
    
    if(dp[x][y] != 0)
    {
        return dp[x][y];
    }
    
    for(int i = 0; i < 2; i++)
    {
        int xpos = x + (dx[i] * map[x][y]);
        int ypos = y + (dy[i] * map[x][y]);    
            
        if(safe(xpos, ypos) == 1)
        {
            dp[x][y] += DFS(xpos, ypos);
        }
    }
    
    return dp[x][y];
}
 
int main(void)
{
//    freopen("B1890_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> map[i][j];
        }
    }
    
    cout << DFS(0, 0);
    
    return 0;
}