백준_1520 내리막길(자바) / DFS + DP

시간 & 메모리 제한

문제

입력 & 출력

DFS + DP를 이용한 문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Back_1520 {
	static int row,col;
	static int[][] map;
	static int[][] dp;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		col = Integer.parseInt(st.nextToken());
		row = Integer.parseInt(st.nextToken());
		
		map = new int[col][row];
		dp = new int[col][row];
		for (int i = 0; i < col; i++) {
			st= new StringTokenizer(br.readLine());
			for (int j = 0; j < row; j++) {
				map[i][j]= Integer.parseInt(st.nextToken());
				dp[i][j]=-1;
			}
		}

		System.out.println(dfs(0,0));
	}
	private static int dfs(int x, int y) {
		if(x==col-1 && y==row-1) {
			return 1;
		}
		if(dp[x][y]!=-1) return dp[x][y];
		
		dp[x][y]=0;
		for (int k = 0; k < 4; k++) {
			int xx = x+dx[k];
			int yy = y+dy[k];
			if(xx<0||yy<0||xx>=col||yy>=row)continue;
			if(map[x][y]>map[xx][yy]) {
				dp[x][y]+=dfs(xx,yy);
			}
		}
		
		return dp[x][y];
	}

}

- 처음에는 DFS로만 풀었는데 메모리 초과가 나왔습니다...

 

- 이 문제의 경우 DFS로만 풀면 경로상에서 중복되는 경로가 많아지게 됩니다..

 

- 이러한 문제를 해결하기 위해서 dp를 통해서 메모리제이션을 하면 중복되는 부분을 최소화 할 수 있었던거 같습니다.