[Baekjoon] 1520번: 내리막 길 - Java

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

1520번: 내리막 길

문제 설명

첫 칸에서 마지막 칸까지 갈 수 있는 모든 경로의 수를 구하면 된다. 단, 항상 높이가 더 낮은 지점으로만 이동한다.

풀이 방법 1. DFS -> 시간 초과

보자마자 DFS로 풀면 되겠다고 생각했고 바로 코딩에 들어갔다. 코딩하면서 이게 왜 정답률이 27%밖에 안 되지? 생각했었는데 왜 그런지 코드를 제출해보고 알게 되었다.

private static void dfs(int x, int y) {
    isVisited[x][y] = true;
    if (x == M - 1 && y == N - 1) {
        answer += 1;
    }

    for (int i = 0; i < 4; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];

        if (nextX >= 0 && nextY >= 0 && nextX < M && nextY < N) {
            if (!isVisited[nextX][nextY] && map[x][y] > map[nextX][nextY])
                dfs(nextX, nextY);
        }
    }

    isVisited[x][y] = false;
}

처음에 30% 정도까지 올라가다가 시간 초과가 발생했다. 왜 그런지 생각해 보았고 결론은 다음과 같았다.

 

M과 N이 500 이하이므로 지도의 최대 크기는 250_000이 된다. 이 경우에 모든 경로를 탐색하게 되어 시간 초과가 발생한 것이라고 추측했다.

 

이 문제를 해결하기 위해 생각해본 것은 다음과 같다.

1. 지나갈 수 없는 경우를 체크해서 다음에 가지 않는 방법
2. 이미 지나왔던 길을 저장해두고 다음에 다시 오지 않는 방법

1번을 먼저 떠올렸고 알고리즘을 생각해봤지만 이내 이 방법은 안 된다는 것을 알았다. 이 방법도 결국엔 모든 칸을 탐색하게 되기 때문이다.

 

2번으로 해결하기 위해서는 DP를 활용해야 했다. DP 문제를 다뤄본 지가 오래 되어 유튜브 강의와 책을 다시 찾아보고 코딩했고 코드는 다음과 같다.

풀이 방법 2. DFS + DP -> 시간 초과

DP를 적용한 방법은 다음과 같다.

1. 지도와 같은 크기의 DP 배열을 만든다.
2. DFS로 경로들을 탐색해 나간다.
3. 탐색을 마친 후 돌아오면서 경로의 개수를 DP에 저장해놓는다.
4. 만약 DP가 0이 아니라면(경로가 있었다면) for 문을 돌지 않고 해당 DP 칸의 값을 반환한다.

private static int dfs(int x, int y) {
    if (x == M - 1 && y == N - 1) {
        return 1;
    }

    if (dp[x][y] != 0) {
        return dp[x][y];
    }

    for (int i = 0; i < 4; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];

        if (nextX >= 0 && nextY >= 0 && nextX < M && nextY < N) {
            if (map[x][y] > map[nextX][nextY]) {
                dp[x][y] += dfs(nextX, nextY);
            }
        }
    }

    return dp[x][y];
}

DP를 활용했음에도 시간 초과가 발생하여 당황했다. 1시간 동안 고민해봤지만 이 부분은 혼자 해결하기 어려울 거라 판단하고 질문 글과 블로그 해설을 보았고 원인을 찾을 수 있었다.

 

위 코드의 7~9번째 줄에서 추측할 수 있듯이 DP 배열을 0으로 초기화했었다. 이것으로 이미 지나왔던 길을 판단하였다. 하지만 여기에서 버그가 발생했다. 원인은 0 자체도 경우의 수의 포함되기 때문이었다. 만약 dp[x][y] = 0 에 해당하는 칸에 도착하면 이 곳이 이미 지나간 곳인지 아니면 경로가 완성되지 않는 곳인지 알 수가 없다. 즉, DP를 적용했지만 또 모든 경우를 탐색해 버린 것이다. 따라서 방문하지 않았음을 나타내는 다른 수로 먼저 초기화 하고 해당 칸에 도착하면 0으로 표시하는 방법을 사용해야 한다. 이를 해결한 코드는 다음과 같다.

풀이 방법 3. DFS + DP(초기화 문제 해결) -> 성공

public static void main(String[] args) throws IOException {
    // ...

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

    // ...
}

private static int dfs(int x, int y) {
    if (x == M - 1 && y == N - 1) {
        return 1;
    }

    if (dp[x][y] != -1) {
        return dp[x][y];
    }
    
    dp[x][y] = 0;

    for (int i = 0; i < 4; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];

        if (nextX >= 0 && nextY >= 0 && nextX < M && nextY < N) {
            if (map[x][y] > map[nextX][nextY]) {
                dp[x][y] += dfs(nextX, nextY);
            }
        }
    }

    return dp[x][y];
}

전체 코드는 다음과 같다.

package baekjoon.dfs_bfs;

import java.io.*;

public class BOJ1520 {

    static int M;
    static int N;
    static int[][] map;
    static int[][] dp;
    static final int[] dx = {0, 1, 0, -1}; // 우하좌상
    static final int[] dy = {1, 0, -1, 0};

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            String[] tokens = br.readLine().split(" ");

            M = Integer.parseInt(tokens[0]);
            N = Integer.parseInt(tokens[1]);

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

            for (int i = 0; i < M; i++) {
                tokens = br.readLine().split(" ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(tokens[j]);
                }
            }

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

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

    private static int dfs(int x, int y) {
        if (x == M - 1 && y == N - 1) {
            return 1;
        }

        if (dp[x][y] != -1) {
            return dp[x][y];
        }

        dp[x][y] = 0;

        for (int i = 0; i < 4; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];

            if (nextX >= 0 && nextY >= 0 && nextX < M && nextY < N) {
                if (map[x][y] > map[nextX][nextY]) {
                    dp[x][y] += dfs(nextX, nextY);
                }
            }
        }

        return dp[x][y];
    }
}