[BOJ - JAVA] 1520 - 내리막 길 (DFS + DP)

# 주소

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

1520번: 내리막 길

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.util.*;
public class Main {
    static int n,m;
    static int dx[] = {1,0,0,-1};
    static int dy[] = {0,1,-1,0};
    static int[][] visit;
    static int arr[][];
    static int count = 0;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n][m];
        visit = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j <m; j++){
                arr[i][j] = scan.nextInt();
                visit[i][j] = -1;
            }
        }
        System.out.println(dfs(0,0));
    }
    public static int dfs(int x, int y) {
        if(x == n-1 && y == m-1){
            return 1;
        }
        if(visit[x][y] != -1){
            return visit[x][y];
        }
        if(visit[x][y] == -1){
            visit[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){
                    if(arr[x][y] > arr[nx][ny]) {
                        visit[x][y] += dfs(nx,ny);
                    }
                }
            }
        }
        return visit[x][y];
    }
}

DFS나 BFS로 풀면 시간초과나서 망합니다.

결론적으로 DP + DFS로 풀어야만 정답을 맞출 수 있습니다.

DFS로 구문을 아무리 짜봐야, 0,0부터 시작해서 똑같은 점을 또 방문할 수 있기 때문에 결론적으로 DFS나 BFS로 풀수가 없습니다.

그러므로 방문한 값이라면 그 인덱스를 초기화 시켜주는 메모이제이션이 필요합니다. 나중에 살펴보겠습니다.

 

DP와 DFS를 같이 활용해서 푸는 문제는 저도 처음이라서 설명이 미숙할 수 있으니 양해부탁드립니다.

 

제일 먼저 arr를 입력 받고 해당 visit을 모두 -1로 저장합니다.

그리고 dfs(0,0)값을 출력하고 dfs구문을 짜보겠습니다.

dfs문은 x == n-1, y == m-1일 때 1을 출력하도록 합니다.

만약 헷갈리신다면 저와 같이 0,0부터 출발해보도록 합시다.

자 0,0입니다. 

 이 그림대로 순조롭게 가본다고 생각해봅시다.

그럼 방문한 저 인덱스들에 대해서는 현재 모두 visit[x][y] = 0인 상태가 된 것입니다.

그리고 dfs함수가 돌아오면서 전부 실행하지 못했던 for문에 대해 각각 실행하기 시작합니다.

그런데 실행하는 것마다 갈 수 있는 더 적은 arr값이 없지요?? 그래서 시작점인 0,0으로 다시 돌아갑니다.

이때, 50 -> 35가 아닌 50 -> 45로 간다면 새로운 루트로 이동할 수 있게 됩니다. (결국 첫번째 dfs함수의 for문이 실행)

그럼 아마 이런 루트로 이동이 가능할텐데요.

여기서 중요한건, 이 함수가 어떻게 동작하는지가 중요합니다.

자, 코딩을 잘 보시면 if(visit[x][y] != -1)일 떄 return visit[x][y];라고 입력했습니다.

이 말은 즉슨, visit[x][y]가 방문한 곳이라면, 더 이상 구문을 진행하지 않고 종료하겠다 라고 해석이 됩니다.

그러니까 어짜피 visit이 -1이 아니란 것은, 방문했다는 뜻이고 그 뒤의 내용은 기존에 이동했던 것처럼 똑같이 이동하면 되니까 굳이 arr들을 비교하지 않으면서 메모리를 아낄 수 있다는 거죠.

그러므로 return visit[x][y]; 이렇게 입력하면 사실상 이 if문을 종료하겠다는 것으로 해석이 가능해집니다.

또한 그로 인해 이하의 if문은 실행되지 않고 거기서 종료되고 이전의 dfs(nx,ny)구문을 다시 실행합니다.

이 문제의 정답은 3인데, 실제로 3이 되려면 세 번째 루트가 있겠죠?

바로 다음과 같습니다.

자 정리를 해보겠습니다.

실제로 if(visit[x][y] != -1){ return visit[x][y]; } 인 지점에 log로 arr[x][y]를 출력해보면 다음과 같습니다.

50
35
30
27
24
22
15
45
37
32
20
17
30
25

이렇게 나옵니다.

50에서 15까지 간 것이 첫 번째 루트이고, 45에서 17까지 간 것이 두 번째, 30 에서 25까지 간 것이 세 번쨰 추가 루트입니다.

확실히 보시면 아시겠지만 2번째 루트에서 17부터 이하의 루트는 이미 방문한 곳이기 때문에 따로 더! 방문할 필요 없이 거기서 종료시키는 것을 알 수 있는데요.

이를 메모이제이션이라고 부릅니다. (함수를 종료시키는 의미로서가 아니라, 함수의 값을 참조하지 않고 함수의 값이 들어있는지를 따지는 행위)

3번째 루트에서도 대뜸 30부터 시작해서(이전 루트는 이미 방문했으므로 필요 없음) 25에서 끝나지요? 이런식으로 추가 경로에 대해서만 따지는 방법을 DP와 DFS를 통해 구현할 수 있었습니다.

확실히 이번 문제는 많은 내용을 포함하고 있습니다.

물론 BFS로도 풀 수 있겠지만 저는 가급적 DFS로 푸는 것을 좀 더 선호하는 편입니다.

아무래도 Queue를 쓰는 것보다 단순 재귀함수로 푸는 것이 더 재밌다고 할까요???

앞으로도 더 좋은 문제로 찾아 뵙겠습니다.

감사합니다.