백준 1520 내리막 길

문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

---

코드

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

class Main {
    public static int count=0;
    public static int[][] dp;

    public static int dfs(int[][] map, int row, int column){
        if(dp[row][column]!=-1)
            return dp[row][column];

        if(row==map.length-1&&column==map[0].length-1)
            return 1;
        else{
            dp[row][column]=0;

            if(row>0&&map[row][column]>map[row-1][column])
                dp[row][column]+=dfs(map, row-1, column);

            if(row<map.length-1&&map[row][column]>map[row+1][column])
                dp[row][column]+=dfs(map, row+1, column);

            if(column>0&&map[row][column]>map[row][column-1])
                dp[row][column]+=dfs(map, row, column-1);

            if(column<map[0].length-1&&map[row][column]>map[row][column+1])
                dp[row][column]+=dfs(map, row, column+1);

            return dp[row][column];
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s=br.readLine();
        StringTokenizer st=new StringTokenizer(s);
        int n=Integer.parseInt(st.nextToken());
        int m=Integer.parseInt(st.nextToken());
        int[][] map=new int[n][m];
        dp=new int[n][m];
        for(int i=0; i<n; i++)
            Arrays.fill(dp[i], -1);
        for(int i=0; i<n; i++){
            s=br.readLine();
            st=new StringTokenizer(s);
            for(int j=0; j<m; j++)
                map[i][j]=Integer.parseInt(st.nextToken());
        }

        bw.write(dfs(map, 0, 0)+"\n");
        bw.flush();
    }
}

---

해결 과정

1. 반복문으로 dfs를 Stack을 사용해서 구현했다. 현재 위치 정보와 가중치를 가지고 있는 Class를 선언하고 그것을 Stack에 넣어서 탐색했다.

2. 메모리 초과(새로운 Class가 계속해서 만들어져서 그런 것 같았다)
   Class를 없애고 재귀적으로 dfs를 구현했다

3. 시간 초과(최악의 경우 4^(500*500)에 근사한 량의 Recursive가 호출된다)
   구글링으로 Dynamic Programming을 처음으로 알게 되고 탐색했던 부분은 더이상 탐색하지 않도록 dp 배열을 만들었다.

4. 😁