백준 1520번 - 내리막 길 (JAVA)

• 문제 출처

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

1520번: 내리막 길

 

 처음 문제보자마자 출처가 고등부 문제라, 쫄고 시작했던 문제. 

 

문제 자체의 설명은 굉장히 명확했다. 따라서, 맨 처음에는 바로 브루트포스 방식을 떠올렸지만, 브루트포스 방식으로 풀었을 때, 굉장히 많은 겹치는 분기가 발생할 것이라고 생각했고 이 분기를 잘 쳐내는게 쟁점이라고 생각했다.

 

 내리막 길을 만들다보면 내리막 길들끼리 필연적으로 길이 겹치게 된다. 하지만, 내리막 길의 특성상 특정 좌표에서 목표 지점까지 가는 경로 방법은, 해당 특정 좌표까지 어떤 길을 걸었던지 모든 분기가 동일하다. 따라서, 좌표마다 값을 부여하여 중복 제거를 하기만하면 문제 티어에 비해 생각보다 쉽게 풀렸다.

 

구체적인 풀이는 다음과 같다.

1.  특정 좌표 값을 입력받으면, 그 좌표로부터 목표지점까지의 내리막 길을 형성하는 dfs를 정의한다. 이때, 목표 지점에 도달하는 순간, 가능한 경로의 수를 의미하는 1을 반환한다. 
2.  각 좌표에서 분기한 결과(해당 좌표에서 출발하여 목표 지점에 도달하는 경로의 수)를 자신의 dp 좌표에 저장한다. 만약, 현재 좌표의 dp 값이 이미 존재한다면, 분기하지 않고 바로 dp 값을 반환한다. 왜냐하면, 어떤 좌표에서 목표 지점까지의 경로의 수를 결정 짓는 것은 현재 y 좌표와 x 좌표가 유일하며, 과거는 영향을 미치지 않기 때문이다. (과거가 영향을 미치지 않는 이유는 내리막 길이라는 특성 때문에 과거에 밟아온 경로가 미래 경로에 영향을 미치지 않기 때문)
3.  (0, 0) 에서 분기한 결과 값을 출력한다.

 

• 정답 코드 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[][] map;
    static int[][] dp;
    static int[] moveY = {0, 0, 1, -1};
    static int[] moveX = {1, -1, 0, 0};
    static int dfs(int y, int x) {
        if (y == map.length - 1 && x == map[0].length - 1)
            return 1;
        else if (dp[y][x] != -1)
            return dp[y][x];

        int tmpSum = 0;
        for (int i = 0; i < 4; i++) {
            int nextY = y + moveY[i];
            int nextX = x + moveX[i];

            if (nextY > map.length - 1 || nextY < 0 || nextX < 0 || nextX > map[0].length - 1)
                continue;
            else if (map[nextY][nextX] < map[y][x]) {
                tmpSum += dfs(nextY, nextX);
            }
        }
        return dp[y][x] = tmpSum;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        map = new int[M][N];
        dp = new int[M][N];

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                dp[i][j] = -1;
            }
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(bf.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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