문제

내리막 길

풀이

DFS 와 DP를 함께 사용해야 하는 문제였다
일단 for 문으로 동서남북 4방향을 전부 방문하는 것 까지는 해결을 했는데 DFS로 모든경로를 전부 방문하려고 하면 stackoverflow 가 발생된다. 그래서 memorization 을 해서 데이터가 존재 하면 경로 하나를 추가하는 방식을 적용해야 한다

1. 2차 배열을 작성한다.

// 방문 횟수를 초기화 한다
int[][] visited = new int[m][n];

// visited 배열을 -1로 초기화 (방문한적 없음)

2. DFS

private static void dfs(int x, int y) {
	// 도착 지점에 도달
	if (x == m - 1 && y == n - 1) {
    	return 1;
    }
    // 이미 방문한 곳이라면 현재 인덱스 방문 횟수를 리턴
    if (visited[x][y] != -1) {
    	return visited[x][y];
    }
    
    // 방문 경로가 없다 = 0
   	visited[x][y] = 0;
    // 동서남북 방향으로 방문한다
    for (int i = 0;i < 4; i++) {
    	int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < m && ny < n) {
        	// 낮은 방향으로 전진 
        	if (map[nx][ny] < map[x][y]) {
            	// 방문 횟수를 더한다
            	visited[x][y] += dfs(nx, ny);
            }
        }
    }
    return visited[x][y];
}

전체 코드

전체 코드