[백준] 1520번 : 내리막 길

문제

 

접근 방식

생긴 거만 봐도 DFS 문제인 것을 알 수 있지만

DFS만으로 풀고 제출하면 시간초과가 발생한다.

 

DFS에 DP까지 활용해야 하는데 아래의 경우를 생각해 보자

 

 

이 사진에서 오른쪽 경우는 왼쪽이 이미 방문한 20부터의 순서를 그대로 반복하는데

이미 갔던 길을 다시 가는 거라면 굳이 또 갈 필요가 없이

해당 구간으로 가는 길에 계산된 값을 그대로 사용하면 된다.

 

즉, 처음 가는 구간이라면 계속해서 도착 지점에 방문할 때까지 탐색하고

탐색 중에 이미 방문한 곳이라면 그 구간에 저장되어 있는 값을 더 해준다.

 

방문 여부를 기록할 불리언 배열은 필요 없고

2차원의 DP 테이블에 값이 채워져 있으면

기존에 방문한 것을 알 수 있기 때문에 이를 활용해서

탐색을 진행해 주면 된다.

 

이번 문제가 아니더라도 반복된 구간을 탐색하는 경우라면

이런 메모이제이션 방식을 사용해도 좋을 것 같다.

 

풀이

class Main {
    
    static int m, n;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int[][] arr, dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());

		arr = new int[m + 1][n + 1];
		dp = new int[m + 1][n + 1];

		for (int i = 1; i <= m; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 1; j <= n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
        
        for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = -1;
			}
		}

		System.out.println(dfs(1, 1));
	}

	static int dfs(int cx, int cy) {
		if (cx == m && cy == n) {
			return 1;
		}

		if (dp[cx][cy] != -1) {
			return dp[cx][cy];
		}

		dp[cx][cy] = 0;

		for (int dir = 0; dir < 4; dir++) {
			int x = cx + dx[dir];
			int y = cy + dy[dir];

			if (x < 0 || x > m || y < 0 || y > n) continue;
			if (arr[x][y] < arr[cx][cy]) {
				dp[cx][cy] += dfs(x, y);
			}
		}

		return dp[cx][cy];
	}
}