[JAVA] BOJ 백준 1520번 - 내리막 길

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

1520번: 내리막 길

---

2. 내가 푼 방법

처음에는 현재보다 작은 숫자만으로 이동하니까 시간초과 안나겠지 하면서 풀었는데.. 아니었다.

 

dp[0][0] = 1; 이라는 base condition 설정해두고 움직일 수 있는 경로 개수를 저장해두는 용도로 dp 배열을 사용했다. 따라서 지도에서 오른쪽 제일 아래 (N-1, M-1)에서 (0, 0)까지 도달할 수 있는 경로를 구해야하므로 현재보다 더 작은 경우에만 이동할 수 있도록 했다.

public static void solution() {
    dp[0][0] = 1;

    result = trace(N-1, M-1);
}

public static int trace(int x, int y)  {
    if (dp[x][y] == -1) {
        dp[x][y] = 0;

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

            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

            if (arr[x][y] < arr[nx][ny]) {
                dp[x][y] += trace(nx, ny);
            }
        }
    }

    return dp[x][y];
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1520.java

import java.util.*;
import java.io.*;

class Main {
    static int N;
    static int M;
    static int[][] arr;
    static int[][] dp;
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {-1, 0, 1, 0};
    static int result;

    public static void main (String[] args) throws IOException {
        init();
        solution();
        print();
    }

    public static void solution() {
        dp[0][0] = 1;

        result = trace(N-1, M-1);
    }

    public static int trace(int x, int y)  {
        if (dp[x][y] == -1) {
            dp[x][y] = 0;

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

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

                if (arr[x][y] < arr[nx][ny]) {
                    dp[x][y] += trace(nx, ny);
                }
            }
        }

        return dp[x][y];
    }

    public static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public 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());
        arr = 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++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

전형적인 DP 문제...였으나 왜 처음부터 알아차리지 못했는지... ㅜ.. 어렵당