1520 내리막 길

BOJ::1520 내리막 길

https://www.acmicpc.net/problem/1520

처음에 단순히 dfs로 풀려 했는데 시간초과가 났다.

그래서 중복방문하는 지점들에 대해 중복으로 방문하지 않도록 하여 풀었다.

d[x][y] ==-1 -> 방문하지 않은 상태

d[x][y] != -1 -> 이미 방문한 상태

#include <stdio.h>
 
int n, m;
int map[500][500];
int d[500][500];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
int dfs(int x,int y) {
    if (x == 0 && y == 0) {
        return 1;
    }
    if (d[x][y] == -1) {
        d[x][y] = 0;
        for (int i = 0; i < 4; i++) {
            int ax = x + dx[i];
            int ay = y + dy[i];
            if (ax >= 0 && ay >= 0 && ax < n && ay < m) {
                if (map[x][y] < map[ax][ay]) {
                    d[x][y] += dfs(ax, ay);
                }
            }
        }
    }
    return d[x][y];
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
            d[i][j] = -1;
        }
    }
    
    printf("%d\n", dfs(n-1,m-1));
}