[백준]JAVA - 1520번: 내리막 길

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

1520번: 내리막 길

풀이

이 문제는 dp를 사용하지 않고 bfs와 dfs를 사용하게 되면 메모리 초과가 발생한다.

그렇다면 dp를 활용해서 메모이제이션을 해주어야한다.

 

예제 1번에서 2, 3번째 방법을 그림으로 보면 메모이제이션을 쉽게 이해할 수 있다.

그림을 보면 알 수 있듯이 20부터 도착지까지 갈 수 있는 방법이 동일하다. 그렇기 때문에 왼쪽 그림처럼 먼저 dfs 탐색을 진행했다면 오른쪽 그림의 경로에선 20부터 도착지까지 갈 수 있는 방법을 dp에 저장해둔 걸 꺼내서 쓰므로 찾는 시간을 줄이는 것이다. 

 

우선 출발지 (0, 0)에서 도착지 (M,N)까지 도달할 수 있는 길의 개수를 찾는 순서는 다음과 같다.

1. 출발지 (0, 0)을 기준으로 dfs 탐색을 시작한다.

2. 배열의 범위를 벗어나거나 내리막 길이 아닌 경우를 제외하고 4방향으로 전진한다.

3. 도착지에 도달했을 경우 1을 return, 처음 방문한 곳이라면 0을 입력 후에 탐색을 진행한다.

 

여기선 보통의 dfs, bfs와 다르게 visited 배열을 만들어서 따로 방문 여부를 체크해주지 않아도 된다. 이유는 내리막 길로만 도착지를 찾아서 가고 있기 때문이다. dp를 통해서 방문처리를 대신하는데 초기에 0이 아닌 -1로 초기화해주어야한다.

 

dfs 탐색이 끝난 후에 dp 배열을 출력해보면 아래와 같이 나온다.

3	2	2	2	1
1	-1	-1	1	1
1	-1	-1	1	-1
1	1	1	1	-1

 

<최종코드>

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

public class Main {
    static int M, N;
	
    static int[][] map;
    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 br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        M = Integer.parseInt(st.nextToken()); // 세로
        N = Integer.parseInt(st.nextToken()); // 가로
		
        map = new int[M][N];
        dp = new int[M][N];
		
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1; // dp 초기화
            }
        }
		
        System.out.println(dfs(0, 0)); // 출발 지점 
    }
	
    public static int dfs(int x, int y) {
        // 도착지점까지 도달했을 경우
        if (x == M-1 && y == N-1) return 1;
		
        // 방문한 적이 없는 경우
        if (dp[x][y] == -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 || nx > M-1 || ny < 0 || ny > N-1) continue;
				
                // 내리막 길인 경우
                if (map[x][y] > map[nx][ny]) {
                    dp[x][y] += dfs(nx, ny);
                }
            }
        }
        return dp[x][y];
    }
}