백준 1520 내리막길 [JAVA]

1520번: 내리막 길

 

풀이 방법

이 문제는 (0,0)에서 출발해 오른쪽 아래인(N-1,M-1)위치까지 내리막길로만 이동해서 도착할 수 있는 경로의 수를 구하는 문제였습니다.

1) DFS로 풀기 -> 시간초과 발생

2) DFS + DP로 풀기

 

처음에는 단순히 DFS로 이 문제를 풀었는데

DFS로 풀 경우, 이미 갔었던 경로를 다시 확인하기 때문에 시간초과가 발생했습니다.

 

그래서 두번째로 푼 방법이 DFS + DP를 이용해 풀었습니다.

(N-1,M-1)위치까지 이동했을 경우에는 DP에 경로의 개수를 저장해 두고, 다른 점에서 또 탐색을 할 경우에 해당 경로를 더해주는 방식으로 구현했습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_BJ_1520_내리막길 {
    
    static int N,M;
    static int [][] map, route;
    
    static int [] dx= {-1,0,1,0};
    static int [] dy= {0,1,0,-1};
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        route = new int[N][M];
        
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                route[i][j] = -1;
            }
        }
        System.out.println(dfs(0,0));
        
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                System.out.print(route[i][j]+" ");
            }
            System.out.println();
        }
    }
    
    public static int dfs(int x, int y) {
        if(x==N-1 && y==M-1) {
            return 1 ;
        }
        
        if(route[x][y]!=-1) return route[x][y];
        
        route[x][y]=0;
        for(int i=0;i<4;i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(range(nx,ny)&&map[nx][ny]<map[x][y]) {
                route[x][y]+=dfs(nx,ny);
            }
        }
        return route[x][y];
    }
    
    public static boolean range(int x, int y) {
        return x>=0 && x<N && y>=0 && y<M;
    }
 
}