자바(백준) 1520 내리막 길

오답 노트 & 새로 알게 된 점

처음 문제 봤을 때, N,M 범위도 작아서 BFS 돌리면 바로 답 나오겠다 라는 생각이 들었다.

그러나 메모리 초과가 났다.

여기서 아.. 메모리 제한이 작구나 하면서 dfs를 사용하면서 혹시 목적지를 출발지로 설정하고

반대로 가면 괜찮지 않을까라는 생각이 들었지만 당연하게도 TLE가 났다.

 

그래서 예시 그림을 자세히 보니 중복해서 지나는 부분이 있었고, dp를 사용하면 되겠다라는 생각까지 했다.

 

하지만 dp 구현을 어떻게 할지 몰라 블로그들의 다양한 풀이를 참고하여 문제를 해결했다.

 

그래도 이제는 어떤 알고리즘을 사용해야할지 감은 오니까 다행인 것 같다.. 

해당 문제와 같은 유형은 (dfs 또는 bfs + dp)는 자주 나올 수 있기 때문에 숙지하고 있어야겠다.

 

처음에 풀이를 보고 문제를 해결할 때, dp의 초기값을 왜 0으로 하면 안될까? 라는 의문을 가지게 됐다.

문제에서는 목적지에 무조건 도착한다는 보장이 없다. 즉, 정답이 0일 수도 있다. 
만약 초기값을 0으로 한다면 0은 "방문"하지 않았다는 로직이 된다. 그래서 TLE가 난다.

따라서 dp의 초기값을 -1로 하여 방문했다는 증거로 0으로 바꿔준다.

 

---

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int row, col;
    static int A[][];
    static int ans;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, 1, -1};
    static int dp[][];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        sb.append(dfs(0, 0));
        System.out.println(sb);
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
    }
 
    static int dfs(int x, int y) {
 
        if(x == row - 1 && y == col - 1) {
            return 1;
        }
 
        if(dp[x][y] > -1){
            return dp[x][y];
        }
 
        dp[x][y] = 0;
 
        for (int i = 0; i < 4; i++) {
            int X = x + dx[i];
            int Y = y + dy[i];
 
            if(!isRangeTrue(X,Y)) continue;
            if(A[X][Y] < A[x][y]){
                dp[x][y] += dfs(X, Y);
            }
        }
 
        return dp[x][y];
    }
 
    static boolean isRangeTrue(int x, int y) {
        return x >= 0 && x < row && y >= 0 && y < col;
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        row = atoi(st.nextToken());
        col = atoi(st.nextToken());
 
        A = new int[row][col];
        dp = new int[row][col];
 
        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                A[i][j] = atoi(st.nextToken());
                dp[i][j] = -1;
            }
        }
    }
}