[백준] 1520. 내리막길

문제

 

풀이

먼저 모든 경로의 수를 구해야하기 때문에 DFS를 사용해 경로를 구했다. 하지만 모든 경우의 수를 탐색하게 되는 경우 시간초과가 발생하기 때문에 이를 줄이기 위한 방법이 필요하다.

생각한 아이디어는 한 번 방문했던 좌표를 x,y라고 했을 때, (x,y) 에서 (N-1, N-1)까지의 경로는 이미 구해져있고 변하지 않기 때문에 다시 탐색할 필요가 없다는 점이다. 따라서 dfs를 진행하며 방문체크를 하고, 방문체크가 된 곳인 경우 저장되어 있는 경우의 수를 그대로 사용함으로써 시간을 줄일 수 있다.

하지만 주의할 점이 있다. 초기 작성한 코드는 다음과 같다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int M, N, total = 0;
    static int[][] map;
    static int[][] cache;
    static int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        M = Integer.parseInt(input[0]);
        N = Integer.parseInt(input[1]);
        map = new int[M][N];
        cache = new int[M][N];

        for (int i = 0; i < M; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(line[j]);
            }
        }
        
        System.out.println(dfs(0, 0));
    }

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

        if (cache[x][y] > 0)
            return cache[x][y];

        for (int i = 0; i < 4; i++) {
            int nX = x + dx[i];
            int nY = y + dy[i];
            if (nX < 0 || nY < 0 || nX >= M || nY >= N || map[x][y] <= map[nX][nY]) continue;
            cache[x][y] += dfs(nX, nY);
        }

        return cache[x][y];
    }
}

이렇게 작성한 경우 시간초과가 발생한다. 이유는 cache[x][y]가 0보다 큰 경우 캐싱된 값을 가져오기 떄문에 문제가 없지만, 0인 경우, 헤당 좌표를 이미 방문했지만 유망하지 않은지 아니면 아직 방문을 하지 않은 지점인지 구분할 수 없기 때문에 여기서 중복 탐색이 발생하기 떄문이다. 이 부분을 방문체크로 변경하여 시간초과를 해결할 수 있다.

최종 풀이는 다음과 같다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int M, N, total = 0;
    static int[][] map;
    static int[][] cache;
    static boolean[][] visited;
    static int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        M = Integer.parseInt(input[0]);
        N = Integer.parseInt(input[1]);
        map = new int[M][N];
        cache = new int[M][N];
        visited = new boolean[M][N];
        for (int i = 0; i < M; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(line[j]);
            }
        }

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

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

        if (visited[x][y])
            return cache[x][y];

        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 >= M || nY >= N || map[x][y] <= map[nX][nY]) continue;
            cache[x][y] += dfs(nX, nY);
        }

        return cache[x][y];
    }
}