백준 1520[자바] java 내리막 길

문제 링크: https://www.acmicpc.net/problem/1520

1520번: 내리막 길

▶문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

 

 

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

---

▶입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈칸을 사이에 두고 주어진다. M과 N은 각각 500 이하의 자연수이고, 각 지점의 높이는 10000 이하의 자연수이다.

---

▶출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

---

▶해설

DP+DFS 문제입니다. 처음에는 DP로만 접근했습니다. 그 결과 상하좌우를 방문하는 순서에 따라서 다른 결과가 나왔습니다. 그래서 DFS개념을 더했습니다.

 

조건을 먼저 보겠습니다.

1. 1,1 출발하여 n,m에 도달하여야 한다.

2. 자신보다 작은 값을 가진 곳으로만 이동할 수 있다.

 

조건만 본다면 DFS로만 풀 수 있겠는데 하겠지만, n, m의 입력값이 500이므로 2^2500의 엄청난 경우의 수를 가지므로, 시간이 초과가 됩니다. 따라서 방문한 곳에 대해서는 값을 메모리 제이 시원한 DP 개념이 더해졌습니다. 

 

상하좌우 4방향으로 이동하므로 y[], x [] 배열을 선언해줍니다. 

 

저는 top down 방식을 활용했습니다. 1,1은 1로 값을 저장해 두고, 나머지 값들은 모두 -1로 저장합니다. 그 후 n, m부터 시작해서 방문한 곳은 0으로 바꾸며, 끝까지 갑니다. 최종적으로 1,1에 도달했을 경우 1을 반환하므로 0이었던 곳이 1로 바뀌며, -1인 곳은 들르지 않게 됩니다. 

예시)

3 3

7 6 5

4 3 4

4 2 1

초기 상태입니다. 그 후 3,3 부터 출발하니 -1인 경우 탐색을 하지 않았으므로 탐색을 진행합니다. 

1	-1	-1
-1	-1	-1
-1	-1	-1

왼쪽 위 모두 방문할 수 있습니다 따라서 0이 들어갑니다. 

1	-1	-1
-1	-1	0
-1	0	0

다음 방문을 진행합니다.

1	-1	0
-1	0	0
0	0	0

다음 방문을 진행합니다. 

1	0	0
0	0	0
0	0	0

최종적으로 1,1에 도달하였으므로 값들을 반환하게 됩니다.

1	1	1
1	3	1
0	3	4

따라서 위와 같은 표가 완성됩니다. 

 

전체 코드

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

public class Main {

    static int[] x = {1, -1, 0, 0}, y = {0, 0, 1, -1};
    static int[][] dp, arr;
    static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        arr = new int[n + 1][m + 1];

        dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            String[] s1 = br.readLine().split(" ");
            for (int j = 1; j <= m; j++) {
                arr[i][j] = Integer.parseInt(s1[j - 1]);
                dp[i][j] = -1;
            }
        }

        System.out.println(solve(n, m));
    }

    public static int solve(int a, int b) {
        if (a == 1 && b == 1) {
            return 1;
        }
        if (dp[a][b] != -1) {
            return dp[a][b];
        } else {
            dp[a][b]=0;
            for (int i = 0; i < 4; i++) {
                int ny = a + y[i];
                int nx = b + x[i];
                if (ny > 0 && ny <= n && nx > 0 && nx <= m) {
                    if (arr[a][b] < arr[ny][nx]) {
                        dp[a][b] += solve(ny, nx);
                    }
                }
            }
        }
        return dp[a][b];
    }
}