[ 백준 1520 ] 내리막 길 - Java

문제 링크

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

1520번: 내리막 길

문제 풀이

dfs+dp 문제이다.

 

처음에는 bfs로 그냥 풀었다가 메모리 초과가 나버렸고, 그냥 dfs로 했다가 시간 초과가 나버렸다.

 

dfs로 쭉 탐색하다가 오른쪽 끝 지점에 도달했을때 1을 리턴하고, 만약에 해당 지점을 탐색한 적이 있을 때 해당 값을 리턴한다.

 

 

소스 코드

 

import java.util.Arrays;
import java.util.Scanner;


public class Main {

	static int [] dx = {-1,1,0,0};
	static int [] dy = {0,0,-1,1};
	static int M,N;
	static int [][] map;
	static int [][] dp;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();

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

		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[0].length; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		for (int i = 0; i < dp.length; i++) Arrays.fill(dp[i], -1);
		dfs(0,0);

		System.out.println(dp[0][0]);
	}

	public static boolean isRange(int x, int y) {
		if(x<0 || y<0 || x>= M  || y>= N) return false;
		return true;
	}

	public static int dfs(int x , int y) {

		if(x==M-1 && y == N-1) return 1;

		if(dp[x][y] == -1) {
			dp[x][y] = 0;
			for(int r = 0; r<4 ; r++) {
				int nx = x+dx[r];
				int ny = y+dy[r];
				if(!isRange(nx, ny)) continue;
				if(map[x][y]>map[nx][ny]) {
					dp[x][y] += dfs(nx,ny);
				}
			}
		}
		return dp[x][y];
	}

}