[JAVA] 백준 1520 내리막 길

 

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

 

문제분석

dp[i][j]를, '(i,j)에서 목적지까지 가는 방법의 합' 으로 저장하면서 사용하는 방식이다. 쌩 DFS로만 구현하면 안되고, dfs를 하면서 한번 방문한 노드는 한번만 계산하고, 추후에 또 계산하면 안되는 조건을 지켜야 시간초과가 나지 않는다. 예를들어

A->B->C

A->D->B->C

가 있으면

B를 2번 계산하는 게 아니라, 첫번째 B 방문에서 계산을 마쳐야 한다.

 

 

코드

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

public class Main {
    static int[][] dp; // [r][c] : 해당 row/col에서 목적지까지 가는 경우의 수
    static int[][] map; // 지도
    static int M; // row
    static int N; // col
    static int[] dr = { -1, 0, 1, 0 };
    static int[] dc = { 0, 1, 0, -1 };

    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());
        dp = new int[M][N];
        map = new int[M][N];

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

    static int DFS(int row, int col) {
        int height = map[row][col];
        if (row == M - 1 && col == N - 1)
            return 1; // 현 위치가 목적지라면 1 return
        if(dp[row][col] != -1) return dp[row][col];
        dp[row][col] = 0; // 계산 전 DP값 0으로 초기화
        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = col + dc[i];
            // 현위치보다 아래라고 판단 시, DFS
            if (nr >= 0 && nc >= 0 && nr < M && nc < N && height > map[nr][nc]) {
                dp[row][col] += DFS(nr, nc); // 해당 방향 가는 경로: [row][col] 에서 건너가는 경우 추가
            }
        }
        return dp[row][col];
    }
}