[BaekJoon] 1520 내리막 길 (Java)

1.  문제 링크

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

2.  문제

요약

• 지도는 직사각형 모양이며 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능합니다.
• 제일 왼쪽 위 칸이 나타내는 지점에서 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 하는데, 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 합니다.
• 지도가 주어질 때, 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 500보다 작거나 같은 자연수인 지도의 세로의 크기 M과 가로의 크기 N이 주어지고 두 번째 줄부터 M개의 줄에는 N개씩 위에서부터 차례로 각 지점의 높이가 주어집니다.
  • 각 지점의 높이는 10,000 이하의 자연수입니다.
• 출력: 첫 번째 줄에 10억 이하의 음이 아닌 정수인 이동 가능한 경로의 수 H를 출력합니다.

3.  소스코드

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

public class Main {
	static int[][] map, dp;
	static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
	static int N, M, possibleNum;
	static void input() {
		Reader scanner = new Reader();
		M = scanner.nextInt();
		N = scanner.nextInt();
		possibleNum = 0;
		map = new int[M][N];
		dp = new int[M][N];
		for(int row = 0; row < M; row++) {
			for(int col = 0; col < N; col++) {
				map[row][col] = scanner.nextInt();
				dp[row][col] = -1;
			}
		}
	}
	
	static void solution() {
		System.out.println(dfs(0, 0));
	}
	
	static int dfs(int x, int y) {
		if(x == M - 1 && y == N - 1) {
			return 1;
		}
		if(dp[x][y] != -1) {
			return dp[x][y];
		}
		dp[x][y] = 0;
		for(int index = 0; index < 4; index++) {
			int cx = x + dx[index];
			int cy = y + dy[index];
			if(cx >= 0 && cx < M && cy >= 0 && cy < N) {
				if(map[x][y] > map[cx][cy]) {
					dp[x][y] += dfs(cx, cy);
				}
			}
		}
		return dp[x][y];
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}