[백준/BOJ] 1520 내리막 길 - JAVA - 골드3

[백준/BOJ] 1520 내리막 길 - JAVA - 골드3

문제

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

문제 분석

조건

• 왼쪽 위에서 시작하여 오른쪽 아래로 이동하는 것이 목표
• 현재 숫자보다 작은 인접한 숫자로만 이동할 수 있음
• 가능한 경로의 수를 출력

풀이방법

• DFS를 이용하여 경로를 탐색하며 DP를 이용하여 방문했던 점엔 다시 방문하지 않는 방법을 이용했습니다.

DP 테이블을 -1로 초기화 한 뒤 출발지점부터 탐색을 시작
현재 좌표에 이미 방문을 했으면 현재 좌표의 DP값을 반환하고, 첫 방문(-1)일 시 0으로 DP값을 업데이트

DFS 탐색을 시계방향으로 했을 때 아래와 같은 상황이 된다.

방법을 반복하여 목표 지점에 도달하였을 경우 1를 반환하고 이를 이전 좌표 DP값에 업데이트 한다.

DP값을 업데이트 하여 돌아갈때 `[0, 3]`좌표에서는 아래 방향으로 한번 더 탐색을 할 수 있게 된다. 이때는 방문하지 않고 방문해야할 지점인 DP[1, 3]의 값을 현재 DP값으로 더하면 된다.
같은 방법으로 계속 진행하여 아래를 탐색하면

위와 같은 모양이 되고, 같은 방법으로 방문해야할 지점의 DP값이 -1이 아니면 해당 값을 현재 DP값으로 더하면 된다.

최종적으로 DP 표는 위와 같은 모양이 되며, `[0, 0]`의 값인 3이 답이 된다.

코드

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

public class Main {
    static int R;
    static int C;
    static int[][] map;
    static int[][] dp;
    static int[][] dr = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

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

        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new int[R][C];
        dp = new int[R][C];
        for (int r = 0; r < R; r++) {
            st = new StringTokenizer(br.readLine());
            Arrays.fill(dp[r], -1);
            for (int c = 0; c < C; c++) {
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }

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

    private static int dfs(int r, int c) {
        if (r == R - 1 && c == C - 1) {
            return 1;
        }
        if (dp[r][c] != -1) {
            return dp[r][c];
        }
        dp[r][c] = 0;
        for (int[] d : dr) {
            int nextR = r + d[0];
            int nextC = c + d[1];
            if (nextR < 0 || nextC < 0 || nextR >= R || nextC >= C) {
                continue;
            }
            if (map[r][c] > map[nextR][nextC]) {
                if (dp[nextR][nextC] != -1) {
                    dp[r][c] += dp[nextR][nextC];
                    continue;
                }
                dp[r][c] += dfs(nextR, nextC);
            }
        }
        return dp[r][c];
    }
}

결과