백준 1520 내리막 길 Java

단계별로 풀어 보기 -> 동적 프로그래밍에 있는 내리막 길 문제이다.

 

이 문제를 풀 때

내가 실수한 점이 몇가지 있다.

 

첫 번째로는 Queue를 사용한 BFS로 풀려고 했다는 점이다.

문제의 내용이 BFS를 사용한 탐색으로 풀어왔던 문제들과 비슷해서

BFS로 풀려고 시도했으나

메모리 초과가 나왔다. 아무래도 Queue를 사용함으로써

메모리 초과가 나온 것 같았다. 

BFS는 대게 최소 횟수 등 최소 값을 구할 때 사용하는데

이 문제에 최소라는 단어는 없다. 그럼 굳이 BFS를 사용할 필요 없이

DFS로 탐색하면 되는 것이었다.

 

두 번째로 중복 방문을 허용했다는 점이다.

내가 중복 방문을 허용한 이유는

예제의 3가지 경우 중 2가지 경우를 보면

1, 3 좌표의 20을 두 번 방문한다.

그렇기 때문에 나는 중복 방문을 허용했었는데

바보 같은 짓이었다.

0, 0부터 출발하는 것이 아니라 n-1, m-1부터

출발하면 쉽게 해결될 문제였다.

 

결론적으로 이 문제는

방문 여부를 체크하면서

dfs로 n-1, m-1부터 0, 0으로 가는 경우를

모두 더해주면 풀리는 문제였다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
 
public class Q1520 {
    public static int [][] a;
    public static int [][] d;
    public static int n;
    public static int m;
    public static int [] tx = {1, -1, 0, 0};
    public static int [] ty = {0, 0, 1, -1};
 
    public static int dfs(int x, int y) {
        if(x==0 && y==0) return 1;
        
        if(d[x][y] == -1) {
            d[x][y] = 0;
            for(int i=0; i<4; i++) {
                if(x+tx[i]>=0 && x+tx[i]<n && y+ty[i]>=0 && y+ty[i]<m) {
                    if(a[x][y] < a[x+tx[i]][y+ty[i]]) {
                        d[x][y] += dfs(x+tx[i], y+ty[i]);
                    }
                }
            }
        }
        return d[x][y];
 
    }
 
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String [] input = reader.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);
        a = new int[n][m];
        d = new int[n][m];
 
        for(int i=0; i<n; i++) {
            input = reader.readLine().split(" ");
            for(int j=0; j<m; j++) {
                a[i][j] = Integer.parseInt(input[j]);
                d[i][j] = -1;
            }
        }
        System.out.println(dfs(n-1, m-1));
    }
}