[알고리즘 - DFS] 백준 1520번: 내리막길 (JAVA)

세상만사 오르막!길 내리막!길

 

 

1520번: 내리막 길

골드 4-5만 전전하다가 큰맘 먹고 한단계 올리기로 결정 골드3 문제입니다

문제를 딱 보자마자 아니 이거 DFS잖아? 

 

일단 DFS갈기고 조건만 사악 걸어줬더니 13%에서 올라가지 않고 시간초과가 떴다

곰인곰인하다가 n, m이 500이고 모든 경로를 확인해서 경우의 수르 찾아야 하니 4^(500*500) 아주 어마무시한 숫자~

 

시간초과가 안나길 바라는 건 양심이 없는 짓이었다 ^.^

곰인곰인하다가 구글링을 해보니 DP와 DFS의 콜라보 문제란다 

아이쿠 그래요? 이걸 근데 어케DP로 풀어용 ㅠ 블로그 글을 봐도 이해가 안돼서 직접 그리면서 결국 이해해냄 히히

 

 

보고 한번에 이해가능한 사람도 있지만 나처럼 이해 못하고 끙끙대고 있을 이 세상에 어떤 사람을 위해 엉망진창이지만 도움이 될 수 있길 바라면서 그린 과정도 넣게씀~

예제에서 2번째 3번째 사진을 기준입니당

 

1. -1로 초기화를 시켜준다

2. n-1, m-1인덱스를 찾으러 가는중 ~ 가면서 처음 방문이면(==-1인 상태) 0으로 바꿔주기

3. n-1, m-1을 찾았다면 retrun 1

    그럼 dp[x][y]+= dfs(n-1, m-1)이니까 지나친 모든 경로들이 모두 1이 됨!

4. 4방향중 갈 수 있는 경로 확인중 아래로 가는 건 했으니 이제 오른쪽으로 갈 차례, 처음 방문이니 0으로 바꿔주면서 n-1, m-1까지 감

5. 목적지 도착하면 3번처럼 1로 바꿔줌 언제까지? 4방향 탐색했던 (0, 3) 까지 

6. (0, 3)에서 dp값은 dp[0][3] + dfs(내 다음 방향의) 이니까 1+1로 2가 됨~ 그리고 이건 0,0까지 계속 반복되니까 다 2로 갱신됨

7. 이제 0,0에서 다른 방향으로 찾고 끝까지 반복 하고 dp[0][0] 값을 반환하면 끝~

 

 

 

/**
 * 백준 1520번 : 내리막길
 * start : 2023-11-13 14:54
 * end : 2023-11-13 15:40
 * 알고리즘 : DFS + DP
 * 한줄평 : 1트 시간초과
 * 그냥 dp로 하면 4^(500*500) 라서 시간초과 나옴
 * dp랑 콜라보레이션해서 풀어야함
 * 경로를 기록하면서 푸는거임~
 */
import java.io.*;
import java.util.*;

public class BJ_1520 {
    static int n, m, cnt;
    static int[][] board;
    static int[][] dp;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new int[n][m];
        dp = new int[n][m];

        for (int i = 0 ; i < n ; i++){
            st = new StringTokenizer(bf.readLine());
            for (int j = 0 ; j < m ; j++){
                board[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }

        dfs(0, 0);
        System.out.println(dp[0][0]);
    }
    public static int dfs (int x, int y){
        if (x == n-1 && y == m-1){
           return 1;
        }

        dp[x][y] = 0;

        for (int i = 0 ; i < 4 ; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >=0 && ny >= 0 && nx<n && ny <m && board[nx][ny] < board[x][y]){
                if (dp[nx][ny] !=-1) dp[x][y] += dp[nx][ny];
                else dp[x][y] += dfs(nx,ny);
            }
        }
        return dp[x][y];
    }
}