[백준/java] 1520번: 내리막길 - DFS + DP

1520번: 내리막길

728x90

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

1520번: 내리막 길

 

1520번: 내리막길

이번 문제는 얼핏보면 단순히 DFS 문제처럼 보인다

 

하지만 제출하고 보면 마주하게 되는 시간초과 행렬을 보면.. 뭐지? DFS 만으로 풀리는 문제가 아닌가 싶은 생각이 든다.

 

시간 초과가 나는걸 보고 이건 단순한 DFS 문제가 아님을 알아야했다.

 

DFS에 DP를 더한 문제였다.

 

DP의 방법은 두가지 방법이 있다.

 

Top Down과 Bottom up 방식이 있는데 그 두가지 방법은 밑의 링크에서 설명되어있다.

https://drcode-devblog.tistory.com/107

 

반응형

 

이 문제를 풀때, Top Down 방식으로 접근을 했다. 보통은 출발위치가 0,0으로 시작하는데

 

나는 탑 다운 방식으로 풀 생각으로 N, M부터 시작해서 현재 위치보다 값이 높으면 언덕을 올라가는 형식으로 풀었다.

 

피보나치 수열을 재귀로 구현하면 fibonacci(N) = fibonacci(N-1) + fibonacci(N-2)를 사용하여 재귀를 풀게 된다.

 

fibonacci 수열을 결국 구하게 되면 fibonacci(0) = 1 이 몇개나 구해지나를 구하는 건데

 

이것 또한 마찬가지로 dfs(0,0)이 얼마나 호출되는지 구하면 된다.

 

1520번: 내리막길

예를 들어 위 그림의 경우, 1행 4열의 32를 보면 갈수 있는 곳이 두 군데임을 볼 수있다.

 

N = 0, M = 3일때,

 

dp[0][3] 은 dfs(N, M+1) + dfs(N+1, M) 이다.

 

왔던 방향은 다시 체크하지 않아도 된다. 

그 이유는 어짜피 현재 위치보다 값이 높으면 반영하지 않기 때문이다.

 

package dfs;

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

public class DownHill {
	static int[][] map, dp;
	static int N, M;
	static int[] dy = { 1, 0, -1, 0 };
	static int[] dx = { 0, 1, 0, -1 };

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

		map = new int[N][M];
		dp = new int[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				map[i][j] = stoi(st.nextToken());
				dp[i][j] = -1;
			}
		}

		int cnt = dfs(N - 1, M - 1);
		System.out.println(cnt);
	}

	public static int dfs(int y, int x) {
		if (y == 0 && x == 0) {
			return 1;
		} else {
			if (dp[y][x] == -1) {
				dp[y][x] = 0;

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

					if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
					if (map[ny][nx] <= map[y][x]) continue;

					dp[y][x] += dfs(ny, nx);
				}
			}

			return dp[y][x];
		}
	}

	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
}