문제링크

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

구현방법

처음에 간단한 DFS를 이용해서 값의 경우의 수를 체크하는 줄 알고 계산을 했었는데 이 경우 현재 500*500 개가 최대기 때문에 4방향체크까지 진행되면 시간초과가 발생했습니다.

DP를 통해서 이전에 지나온 곳의 중복된 길 체크가 발생하지 않게 0으로 변화시켜서 체크하며 진행했습니다.

구현알고리즘

dfs + dp

CODE

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

public class Main {

    static int result = 0;


    static int dx[] = {0,-1,0,1};
    static int dy[] = {-1,0,1,0};

    static int map[][];

    static int dp[][];
    static int N,M;


    public static void main(String[] args) 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());
        map = new int[N][M];
        dp = new int[N][M];
        for(int rows = 0; rows <N;rows++)
        {
            st = new StringTokenizer(br.readLine());
            for(int cols = 0; cols <M;cols++)
            {
                map[rows][cols] = Integer.parseInt(st.nextToken());
                dp[rows][cols] = -1;
            }
        }

        result = starting(0,0);

        System.out.println(result);
    }

    private static int starting(int row, int col) {
        if(row == N-1 && col == M-1){
            return 1;
        }
        //이미 온곳은 다시 탐색 x
        if(dp[row][col] != -1)
            return dp[row][col];

        dp[row][col] = 0;
        for(int idx= 0; idx < 4 ;idx++){
            int nxt_row = row + dx[idx];
            int nxt_col = col + dy[idx];

            //맵을 벗어나거나 다음 값보다 작은 경우 패스
            if(nxt_row < 0 || nxt_row >= N || nxt_col < 0 || nxt_col >= M || map[row][col] <= map[nxt_row][nxt_col]){
                continue;
            }
            dp[row][col] += starting(nxt_row,nxt_col);
        }
        //4방향 전부 체크하고 업데이트
        return dp[row][col];
    }
}