[BAEKJOON] 1520 내리막길

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> using namespace std; //시간초과 int row, col; vector<vector<int>>map, DP; int stair(int x, int y) { int&ret = DP[x][y]; if (x == row - 1 && y == col - 1) return ret = 1; if (ret != -1) return ret; ret = 0; int num1=0, num2=0, num3=0, num4=0; if (x + 1 < row && map[x + 1][y] < map[x][y]) num1 = stair(x + 1, y); if (y + 1 < col && map[x][y + 1] < map[x][y]) num2 = stair(x, y + 1); if (x - 1 >= 0 && map[x - 1][y] < map[x][y]) num3 = stair(x - 1, y); if (y - 1 >= 0 && map[x][y - 1] < map[x][y]) num4 = stair(x,y - 1); return ret = num1 + num2 + num3 + num4; } int main() { map = vector<vector<int>>(501, vector<int>(501)); DP = vector<vector<int>>(501, vector<int>(501, -1)); scanf("%d %d", &row, &col); for (int x = 0; x < row; x++) for (int y = 0; y < col; y++) scanf("%d", &map[x][y]); printf("%d", stair(0, 0)); return 0; }

처음에 DP를 0으로 초기화를 해서 틀렸다

음..아직까지 왜 틀렸는지 모르겠다..

아마 0으로 visit를 표시하는 것 같은데 

이것도 일종의 DFS이기 때문이다.

http://blog.eairship.kr/268 : 이 블로그에서 DFS를 공부했다.