[BaekJoon] 1520 내리막 길 (Java)

🔗 문제 링크

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

📝 문제 풀이 설명

처음 문제를 풀이할때는 기본적인 DFS를 적용하여 문제를 풀었다.
하지만 문제에 제한된 시간이 적어 DFS만으로 풀 경우 시간초과라는 결과를 얻어서 Dynamic Programming형식으로 문제를 풀어야한다.

DFS방식에서 DP를 적용은 한번 방문한 위치의 경우 해당 위치에서 종료지점까지 몇개의 경로가 존재하는지 저장을 하고 다시 그 지점을 방문할 경우 새로운 탐색을 할 필요 없도록 하였다.

예를 들어 예제에서 matrix[2][3]에서 종점인 matrix[3][4]로 이동할 경우 처음 방문할때만 DFS를 통해 해당 지점으로부터 종점까지 몇개의 길이 있는지 탐색을 하고 다음번부터는 탐색을 할 필요가 없도록 합니다.

코드는 다음과 같습니다.

👨🏻‍💻 DFS로만 작성한 코드 (시간초과)

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

public class Main {
	
	static int M;
	static int N;
	static int[][] matrix;
	static boolean[][] checked;
	static int result;
	static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		matrix = new int[M][N];
		checked = new boolean[M][N];
		
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=0; j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		result = 0;
		checked[0][0] = true;
		dfs(0, 0);

		System.out.println(result);
	}
	
	
	static void dfs(int y, int x) {
		if (y==(M-1) && x==(N-1)) {
			result++;
		}
		else {
			int currentHeight = matrix[y][x];
			for (int i=0; i<4; i++) {
				int cx = x+dx[i];
				int cy = y+dy[i];
				if (0 <= cx && cx < N && 0 <= cy && cy < M && !checked[cy][cx] && matrix[cy][cx] < currentHeight) {
					checked[cy][cx] = true;
					dfs(cy, cx);
					checked[cy][cx] = false;
				}
				
			}
		}
	}

}

👨🏻‍💻 DFS+DP로 작성한 코드 (통과)

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

public class Main {
	
	static int M;
	static int N;
	static int[][] matrix;
	static int[][] dp;
	static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		matrix = new int[M][N];
		dp = new int[M][N];
		
		for (int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=0; j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
				dp[i][j] = -1; // 방문하지 않은 곳은 -1로 초기화
			}
		}
		
		System.out.println(dfs(0, 0));
	}
	
	
	static int dfs(int y, int x) {
		if (y==(M-1) && x==(N-1)) {
			return 1;
		}
		if (dp[y][x] != -1) return dp[y][x];
		
		
		// 현재 값 초기화
		dp[y][x] = 0;
		for (int i=0; i<4; i++) {
			int cx = x+dx[i];
			int cy = y+dy[i];
			
			if (0 <= cx && cx < N && 0 <= cy && cy < M) {
				if (matrix[cy][cx] < matrix[y][x]) {
					dp[y][x] += dfs(cy, cx);
				}		
			}
		}
		return dp[y][x];
	}

}