[1520] 내리막 길

처음에 dfs로 풀었는데 당연하게도 시간초과가 떠서 dp로 생각하느라 오래걸렸던 문제다.

상,하,좌,우 네 방향을 전부 검사하면서 재귀로 값을 리턴받는다.

이렇게 이동한 후 끝지점에 도달했을 때 1을 리턴 받으므로 이동했던 경로(A)에 전부 1이 들어가게 된다.

그 후 다른 경로(B)로 이동하다가 전에 거쳤던 경로와 겹치게 되면 (D테이블의 값이 0보다 크면)

겹친 경로는 다시 가볼 필요없이 D테이블 값을 리턴해서 이동해온 경로(B)에 더해준다.

모든 경로를 거쳤을 때 d[0][0]에 갈 수 있는 경우의 수가 저장된다.

---

#include <cstdio>

using namespace std;

int t[501][501];

int d[501][501];

int res;

int downHill(int row, int col, int maxRow, int maxCol)

{

int dx[4] = {-1, 0, 1, 0};

int dy[4] = {0, 1, 0, -1};

if (row == maxRow && col == maxCol)

{

return 1; //끝에 도달하면 1리턴

}

if(d[row][col] >= 0){

return d[row][col]; //이미 계산한값이면 d테이블값 리턴

}

if (d[row][col] == -1)

d[row][col] = 0; //처음 검사할 때 0 대입

for (int i = 0; i < 4; i++)

{

if(row + dx[i] >= 0 && row + dx[i] <= maxRow && col + dy[i]>=0 && col + dy[i] <= maxCol)

if (t[row + dx[i]][col + dy[i]] < t[row][col])

d[row][col] += downHill(row + dx[i], col + dy[i], maxRow, maxCol); //재귀로 움직이며 d값 더함

}

return d[row][col];

}

int main()

{

int row, col = 0;

scanf("%d %d", &row, &col);

for (int i = 0; i < row; i++)

{

for (int j = 0; j < col; j++)

{

d[i][j] = -1;

scanf("%d", &t[i][j]);

}

}

downHill(0,0,row-1,col-1);

printf("%d\n", d[0][0]);

}