DFS + DP (백준 1520 내리막길)

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

1520번: 내리막 길

 

풀이과정

(r,c)에서 목적지 (M-1,N-1)까지 갈 수 있는 모든 경로의 갯수는

(r,c)와 인접한 (nr,nc)에서 목적지 (M-1,N-1)까지 갈 수 있는 경로 갯수의 합이다.

위 과정을 그림으로 나타내면 아래와 같다

 

 

 

보통의 bottom-up 방식으로 구현하는 dp가 아니었다.

 

메모리제이션 방법

방문체크 배열(visited) 을 둬서 계산이 완료된 좌표의 경우 계산된 결과값을 리턴하는 방식으로 메모리제이션을 구현했다.

static int solve(int r,int c){

        if(r==M-1 && c==N-1){
            return 1;
        }

        if(visited[r][c]){ // 방문한 적이 있으면 결과 리턴 (중복연산 줄임)
            return memo[r][c]; 
        }

        visited[r][c]=true; // 방문처리

        for(int d=0;d<4;d++){
            int nr = r + dr[d];
            int nc = c + dc[d];
            if(nr<0 || nr>=M) continue;
            if(nc<0 || nc>=N) continue;

            if(arr[r][c] > arr[nr][nc]){
                memo[r][c] += solve(nr,nc);
            }
        }

        return memo[r][c];
    }

 

전체코드

package com.mincheolsong;
import java.io.*;
import java.util.*;


public class Main {
    static int M,N;
    static int[][] arr;
    static int[][] memo;
    static int[] dr = {-1,0,1,0};
    static int[] dc = {0,1,0,-1};
    static boolean[][] visited;

    static int solve(int r,int c){

        if(r==M-1 && c==N-1){
            return 1;
        }

        if(visited[r][c]){ // 방문한 적이 있으면 결과 리턴 (중복연산 줄임)
            return memo[r][c]; 
        }

        visited[r][c]=true; // 방문처리

        for(int d=0;d<4;d++){
            int nr = r + dr[d];
            int nc = c + dc[d];
            if(nr<0 || nr>=M) continue;
            if(nc<0 || nc>=N) continue;

            if(arr[r][c] > arr[nr][nc]){
                memo[r][c] += solve(nr,nc);
            }
        }

        return memo[r][c];
    }

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

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

        arr = new int[M][N];
        memo = new int[M][N]; // memo[0][0] : (0,0)에서 (M-1,N-1)까지 갈 수 있는 경우의 수를 저장
        visited = new boolean[M][N];

        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.println(solve(0,0));
    }

}