[백준 / 골드3] 1520 내리막 길 (Java)

문제 보기

사용한 것

• 시작 지점에서 목표 지점까지 내리막길만 사용하여 도달 가능한 경우의 수를 구하기 위한 top-down

풀이 방법

• 현재 좌표를 이미 방문한 경우
  • memo return
• 현재 좌표를 방문하지 않은 경우
  • visited true
  • 현재 좌표에서 동, 서, 남, 북으로 도달 가능하고 오르막길이면 해당 경우의 수를 재귀호출하여 모두 더해줌
  • memo에 넣고 return

코드

public class Main {

    private static final int[] DX = {-1, 0, 1, 0};
    private static final int[] DY = {0, 1, 0, -1};
    private static int n;
    private static int m;
    private static int[][] map;
    private static boolean[][] visited;
    private static int[][] memo;

    public static void main(String[] args) throws IOException {
        init();
        System.out.println(findNumOfPaths(n - 1, m - 1));
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        memo = new int[n][m];
        visited = new boolean[n][m];
        memo[0][0] = 1;
        visited[0][0] = true;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    private static int findNumOfPaths(int x, int y) {
        if (visited[x][y]) {
            return memo[x][y];
        }
        visited[x][y] = true;

        int numOfPaths = 0;
        for (int i = 0; i < 4; i++) {
            int nx = x + DX[i];
            int ny = y + DY[i];

            if (isOOB(nx, ny) || map[nx][ny] <= map[x][y]) {
                continue;
            }

            numOfPaths += findNumOfPaths(nx, ny);
        }

        return memo[x][y] = numOfPaths;
    }

    private static boolean isOOB(int x, int y) {
        return x < 0 || x >= n || y < 0 || y >= m;
    }
}