백준 - 1520

문제

입력/출력

풀이

상하좌우의 칸에 현재 값과 비교를 하기위해 dx/dy를 쓰고,
계산 시간 단축을 위해 동적 계획법을 사용한다.

?)동적 계획법:중복되는 지점들을 캐싱하여 중복 계산을 줄여서 효율성을 높이는 방법

1부터 5까지의 경로 수를 구할 때 3까지 가는 경로의 수를 저장하여 중복계산을 줄인다

dp의 값을 모두 -1로 초기화한다. 탐색을 할때 map과 같은 좌표의 dp 값이 -1인 경우와 아닌 경우를 구별한다.
-1인 경우에는 한번도 방문하지 않은 경로라는 의미기 때문에 같은 값의 지도 좌표에서 4방탐색하여 더 작은 곳이 있는지 확인하고 작은 곳으로 이동한다. 이때 경로의 수를 더 해준다.
dp가 -1이 아닌 경우는 현재 dp에 저장된 값을 반환해준다.

코드

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

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken()); //가로
        N = Integer.parseInt(st.nextToken()); // 세로

        map = new int[M + 1][N + 1];
        dp = new int[M + 1][N + 1];
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken()); // 지도 좌표 입력
                dp[i][j] = -1; // dp는 모든 값을 -1로 초기화
            }
        }
        System.out.println(DFS(1,1));
    }



    public static int DFS(int x, int y) {
        if (x == M && y == N) {
            return 1;
        }
        if(dp[x][y]!=-1){ //방문한 칸이면 리턴하여 계산 시간 단축
            return dp[x][y];
        }
        else {// -1 일때만 방문
            dp[x][y] = 0; //방문 표시
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 1 || ny < 1 || nx > M || ny > N) { // 4방 탐색 범위설정
                    continue;
                }
                if (map[nx][ny] < map[x][y]) { //현재 값이 4방 탐색 값보다 큰 경우
                    dp[x][y] += DFS(nx,ny); // 현재까지의 경로의 수를 저장
                }
            }
        }
        return dp[x][y]; 총 경로 경우의 수 반환
    }
}

오답 코드 (시간 초과) dp를 사용하지않는 경우

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

class Main {
    static int M, N;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int count = 0;

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        map = new int[M + 1][N + 1];
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        DFS(1, 1);
        System.out.println(count);
    }

    public static void DFS(int x, int y) {
        if (x == M && y == N) {
            count++;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 1 || ny < 1 || nx > M || ny > N) {
                continue;
            }
            if (map[nx][ny] < map[x][y]) {
                DFS(nx, ny);
            }
        }
    }
}