[DFS+DP] 백준 1520번 내리막 길 - JAVA

 

DFS와 DP의 조합은 어렵다 ㅠ

다시 공부해야짓!

 

---

1. 출처

---

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

1520번: 내리막 길

 

• 지도 상에 건물의 높이가 주어짐
• 높이가 현재 건물보다 낮은 곳만 이동할 수 있음
• 내리막길로만 가고 싶음 (우, 하, 좌)
• 갈 수 있는 경로는 몇 개인지 계산하는 문제

 

 

---

2. 설계

---

 

처음엔 BFS로 좌, 하, 우 방향 탐색해서 갈 수 있는 경로가 몇 개인지 계산하고자 하였다. 그런데 16%만에 메모리 초과가 났다.

가로x세로 = 500x500이기 때문에 큐에 들어가는 메모리가 상당히 크다는 것을 인지하지 못했다.

 

어떻게 풀어야할지 감도 잡히지 않았다. 메모리를 어떻게 줄이지? 그럼 큐를 쓰지 말아야하는데, DFS는 시간도 더 오래걸리고... DP로 하자니 공식이 없어보이는데 어쩌지? 라는 생각만 가득했다. 그래서 답을 보게 되었다.

 

고수들은 DFS+DP를 사용하여 DFS의 시스템 콜을 부르는 시간을 단축시켰다.

 

 

1) dp 초기화

dp 배열을 -1로 초기화해줄 것이다.

그 이유는 경로 수가 0인 곳도 있을 것이고, -1이라는 의미는 계산된 적 없는 경로임을 뜻하게 하기 위함이다.

dp = new int[M][N];
for(int i=0; i<M; i++){
	Arrays.fill(dp[i],-1);
}

 

 

2) DFS + DP

• 도착지 (M-1, N-1) 위치에 도착하면 하나의 경로를  찾았다는 의미로 부모 스레드에 1을 리턴할 것이다.
• 위에서 말했던 것처럼 dp가 -1이 아니면 경로를 계산한 적 있다는 의미로 DFS로 시스템 콜을 호출하지 않고, 계산된 경로를 리턴한다.
• 두 경우에 포함되지 않는다면 이번 경로를 계산하기 위해 0으로 초기화하고, DFS를 보낸다.
  • 단, map 범위 내여야 한다.
  • 현재 빌딩 건물 높이보다 다음 건물 높이가 낮아야 한다.
• 상하좌우 4방향을 탐색하여야 한다. 하좌우 3방향만 판단하면 오답으로 나온다.

public static int DFS(int r, int c){

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

        if(dp[r][c]!=-1){
            return dp[r][c];
        }

        dp[r][c] = 0;//초기화

        for(int d=0; d<4; d++){
            int nextR = r+drc[d][0];
            int nextC = c+drc[d][1];
            
            if(nextR<0 || nextR>=M || nextC<0 || nextC>=N) continue;
            if(map[nextR][nextC]>=map[r][c]) continue;
            
            dp[r][c] += DFS(nextR, nextC);
        }

        return dp[r][c];
}

 

 

3) 결과 출력 주의

dp[M-1][N-1]은 정답이 아니다.

모든 시작은 (0,0)에서 시작했다. 그래서 최종 결과가 return되어 dp[0][0]에 쌓이게 되는 것이다.

그런 이유로 정답은 dp[0][0] 혹은 DFS(0, 0)을 호출하여 그대로 반환해주는 값을 가져오면 된다.

 

아래는 테스트를 위한 Draw 모듈이다.

public static void Draw(){
        for(int r=0; r<M; r++){
            for(int c=0; c<N; c++){
                System.out.printf(dp[r][c]+" ");
            }
            System.out.println();
        }
        System.out.println();
}

 

 

아래는 실행 결과이다.

//예제 1 정답
3

//Draw 결과
3 2 2 2 1 
1 -1 -1 1 1 
1 -1 -1 1 -1 
1 1 1 1 -1

 

 

---

3. 전체 코드

---

 

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

class Main {
    
    static int[][] drc = {{-1,0}, {1,0},{0,-1},{0,1}};
    static int[][] map, dp;
    static int M,N;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String MN = br.readLine();
        StringTokenizer st = new StringTokenizer(MN, " ");
        
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        map = new int[M][N];
        for(int r=0; r<M; r++){
            String line = br.readLine();
            st = new StringTokenizer(line, " ");
            for(int c=0; c<N; c++){
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        //입력 끝

        dp = new int[M][N];
        for(int i=0; i<M; i++){
            Arrays.fill(dp[i],-1);
        }

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

    public static int DFS(int r, int c){

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

        if(dp[r][c]!=-1){
            return dp[r][c];
        }

        dp[r][c] = 0;//초기화

        for(int d=0; d<4; d++){
            int nextR = r+drc[d][0];
            int nextC = c+drc[d][1];
            
            if(nextR<0 || nextR>=M || nextC<0 || nextC>=N) continue;
            if(map[nextR][nextC]>=map[r][c]) continue;
            
            dp[r][c] += DFS(nextR, nextC);
        }

        return dp[r][c];
    }
}