[백준/1526] - 내리막길(JAVA)

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

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

 

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

입력

---

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

 

출력

---

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

 

풀이

---

public class Main {

    static int N, M;
    static int[][] field;

    static int[][] dp;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        dp = new int[N][M];
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++){
                field[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }
        //DFS
        System.out.println(DFS(0,0));
    }
    static int DFS(int x, int y){
        if (x == N-1 && y == M-1){
            return 1;
        }
        if (dp[x][y] != -1){
            return dp[x][y];
        }

        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){
                if (field[nx][ny] < field[x][y]){
                    dp[x][y] += DFS(nx, ny);
                }
            }
        }

        return dp[x][y];
    }
}

해설

---

https://choincnp.tistory.com/88

[백준/1987] - 알파벳(JAVA)

알파벳 문제가 DFS+DP의 맛보기라면, 이번 내리막길 문제는 본격적으로 DFS+DP를 이용하는 문제이다.

물론 DFS만 이용해서 문제를 풀 수도 있다. 그러나 문제는 시간 초과가 발생한다.

가로와 세로가 500x500까지 주어질 수 있어서, 모든 루트를 다 거쳐갈때 5초라는 시간이 발생하지만 시간 제한은 2초이기 때문이다.

<DFS만을 이용한 풀이법>

 

public class Main {

    static int N, M, answer;
    static int[][] field;
    static boolean[][] visited;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        visited = new boolean[N][M];
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++){
                field[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //DFS
        DFS(0,0,field[0][0]);

        System.out.println(answer);
    }
    static void DFS(int x, int y, int number){
        if (x == N-1 && y == M-1){
            answer++;
        }
        visited[x][y] = true;
        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 (!visited[nx][ny] && field[nx][ny] < number){
                    DFS(nx, ny, field[nx][ny]);
                }
            }
        }
        visited[x][y] = false;
    }
}

그럼 지금부터 DP의 Top-down 방식을 이용한 풀이를 해 보자.

static int N, M;
static int[][] field;
static int[][] dp;
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};

먼저, 가로와 세로 길이인 N, M을 선언하고, 값을 입력받을 field와 dp 배열을 선언한다.

마지막으로, 길은 상하좌우로 찾아나갈 것이므로 델타배열을 선언한다.

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        field = new int[N][M];
        dp = new int[N][M];
        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<M; j++){
                field[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }
        //DFS
        System.out.println(DFS(0,0));
    }

메인스택 자체는 단순하다. 적절하게 변수를 초기화시켜주고,

int배열로 dp배열을 선언하였으므로, -1로 배열을 초기화해준다.

마지막으로 DFS함수만 print해주면 된다.

static int DFS(int x, int y){
        if (x == N-1 && y == M-1){
            return 1;
        }
        if (dp[x][y] != -1){
            return dp[x][y];
        }

        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){
                if (field[nx][ny] < field[x][y]){
                    dp[x][y] += DFS(nx, ny);
                }
            }
        }

        return dp[x][y];
    }

DFS펑션이다. 

먼저 시작지점에서 끝지점까지 가는 방법의 수 자체를 출력해야 하므로, 끝 지점에 도달하였다면(x == N-1 && y == M-1)

1을 리턴하자.

최단 경로가 dp배열에 이미 기록되어있다면 바로 dp배열의 값을 리턴해준다.

마지막으로, 도달하였을경우 dp배열에 값을 0으로 바꿔주고(DFS에서 했던 visited와 비슷한 역할)

 

델타배열을 이용한 새 좌표를 구한 후 최소값으로 이동할 경우 dp배열에 DFS값을 더해준다.

만약 [x,y]발판 이후로 [N-1, M-1]까지의 경로가 존재할 경우 1이 더해질 것이고, 아니라면 아무 행동도 일어나지 않을 것이다.

Arrays.deepToString(dp) = [[3, 2, 2, 2, 1], [1, -1, -1, 1, 1], [1, -1, -1, 1, -1], [1, 1, 1, 1, -1]]

DFS를 실행시키고 난 다음 dp배열을 찍어보면 위와 같이 나온다.

이 dp배열의 뜻은 [x,y] -> [N-1, M-1]까지 가는 최단경로가 몇개나 나올 수 있을지를 찍는 배열이다.

DP는 아직 많이 학습하지 않았으므로, 나중에 따로 포스팅하겠다.