BOJ G3 1520 내리막길 JAVA

1520번: 내리막 길

---

문제 읽기

처음에 봤을 때는 어제 풀었던 점프랑 뭔가 비슷하다는 느낌이 들었다.

 

BOJ_S1_1890_점프

 

하지만 점프의 경우에는 단순히 오른쪽, 아래쪽 방향으로만 이동이 가능했지만, 이 문제의 경우에는 상하좌우 모든 방향에 대해 이동이 가능했고, 숫자가 더 작은 곳으로만 이동할 수 있다는 제약 조건이 있었다. 따라서 어제처럼 단순히 DP만 써서 풀 수는 없을 거라고 생각했다. (방법이 있을 수도 있겠지만 떠오르진 않았다.)

 

단순히 DP로만 풀 수 없다면 어떻게 풀어야 할까.. 고민하다가 질문 게시판을 조금 참조해서 DFS + DP로 방향을 정했다. 이 유형은 많이 해보지 않아서 조금 막막했다. 그냥 DP 특성을 이용해서 중복된 계산을 줄이는 방식으로 접근하자는 생각을 가지고 임했다.

 

---

문제 풀기

제약 조건 파악

우선 입력 값의 범위나 제약 조건들을 봤을 때 long을 써야 한다던지 하는 특별한 경우는 없었다. 그냥 로직만 잘 짜면 되는 것 같다.

 

삽질을 한 번 했다. 그래도 실패의 이유를 깨달은 유익한 삽질..

 

첫 번째 접근 : DP를 boolean으로 → 오답

우선 DFS를 하고, 여기에서 백트래킹처럼 DP를 이용해서 줄일 수 있는 방법을 찾아야 한다. 사실 DP는 이미 구한 값을 이용하는 것이기 때문에 따지자면 백트래킹과는 다르지만, 어쨌든 연산을 줄인다는 점에서는 같다.

 

그래서 처음에는 DFS를 수행하며 특정 루트를 따라 최종 목적지에 도달하는 데에 성공했다면, 리턴을 수행하면서 DP의 해당 루트 좌표에 다 true를 담아주었다. 그리고 계속 DFS를 수행하며 다른 루트를 타면서 DP를 계속 확인하다가, DP 값이 true이면 이미 탐색한 루트이기 때문에 다시 탐색하지 않고 루트 카운트에 +1을 해주었다.

 

이런 식으로 하고 제출했는데 10% 쯤에서 “틀렸습니다”가 나왔다.

틀린 이유에 대해서 질문 게시판을 참고했는데, 나와 비슷한 사람이 있었고 그 답변이 도움이 됐다.

글 읽기 - [질문] DFS+DP 방식으로 풀었는데 12%에서 틀렸다고 뜹니다..

이 답변을 보고 DP 배열을 boolean이 아니라 int로 바꿔야겠다는 생각을 했다.

 

두 번째 접근 : DP 배열을 int로 → 성공

DP 배열을 int로 바꾼 후, 현재에서 갈 수 있는 네 방향의 길에 대해 DFS를 수행하였고, 이미 방문해서 계산한 값이면 DP 값을 이용해 더해주었다. 순차적으로 정리하면 다음과 같다.

1. DFS(0, 0)에서 탐색 시작
2. 현재 위치가 마지막 위치이면 return 1 (도달했으므로 루트 + 1)
3. 네 방향 탐색
   1. 이미 방문한 곳
      1. dp[r][c] += dp[nr][nc] - 다시 계산하지 않고 DP값 이용
   2. 새로운 곳
      1. dp[r][c] += dfs(nr, nc) - DFS 수행
4. return dp[r][c]

즉, DFS 함수를 수행하면서 DP 배열을 채우게 되는 것이고, DFS 함수의 반환 값은 DP 배열의 원소가 되면서 이를 이용하여 중복된 계산을 줄이고 있다.

이를 수행하면 다음과 같은 DP 배열이 나온다.

직접 그려봐도 좋을 것 같다!

DP[0][0]의 값이 답이 된다.

---

코드

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

public class Main {
    static int N, M;
    static int[][] map;
    static int[][] dp;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

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

        //logic
        dp = new int[N][M];
        visited = new boolean[N][M];
        dfs(0, 0);

        System.out.println(dp[0][0]);
    }

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    private static int dfs(int r, int c) {
//        System.out.println(r + " " + c);
        if (r == N-1 && c == M-1) {
            dp[r][c] = 1;
            return 1;
        }

        //주변으로 이동
        for (int di = 0; di < 4; di++){
            int nr = r + dr[di];
            int nc = c + dc[di];
            if (nr < 0 || nr >= N || nc < 0 || nc >= M || map[r][c] <= map[nr][nc]) continue;

            if (visited[nr][nc]){
                dp[r][c] += dp[nr][nc];
            }
            else{
                visited[nr][nc] = true;
                dp[r][c] += dfs(nr, nc);
            }
        }
        return dp[r][c];
    }
}