1520. 내리막 길

평소처럼 dfs/bfs로 풀었지만 시.간.초.과..

500 * 500 이라서 될 줄 알았지만, 모든 인덱스 위치에서 모든 경우를 다 계산해야 하기에 최대 500 * 500마다 500 * 500이 될 수 있으므로 250000 * 250000 가 되어 시간초과가 당연히 발생되는 것이다.

시간을 줄이고자 방문해서 도착지점에 도착했던 경로는 당연히 나중에도 그 길을 통해 도착이 보장되므로 그 길을 다시 확인하는 수를 줄여야겠다고 생각했다.

dfs의 return값을 통해 방문과 함께 갈 수 있는 길의 수를 구하기 위해 dp와 dfs를 함께 이용해 풀었다.

 

package october.oneweek;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class B_1520_내리막길 {
 
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int[][] arr = new int[M][N];
        int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
        int[][] visited = new int[M][N];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(in.readLine(), " ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                visited[i][j] = -1; // 방문되지 않을 시
            }
        }
        System.out.println(dfs(0, 0, M, N, arr, dir, visited));
    }
 
    private static int dfs(int y, int x, int M, int N, int[][] arr, int[][] dir, int[][] visited) {
        if (y == M - 1 && x == N - 1) // 도착지점 도착
            return 1;
 
        if (visited[y][x] == -1) { // 미방문(-1)일 때
            visited[y][x] = 0; // 방문 표시
            for (int i = 0; i < 4; i++) {
                int my = y + dir[i][0];
                int mx = x + dir[i][1];
                if (my < 0 || mx < 0 || my >= M || mx >= N)
                    continue;
                if (arr[my][mx] < arr[y][x]) { // 더 낮은 위치의 조건 만족 시
                    visited[y][x] += dfs(my, mx, M, N, arr, dir, visited);
                }
            }
        }
        // 이미 방문 기록이 있다면 (visited[y][x] != 0) or 미방문 처리 후
        return visited[y][x];
    }
 
}