[백준] 1520번 - 내리막 길 (Java)

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

1520번: 내리막 길

 

<문제 분석>

1. map에는 높이 정보가 주어지고, 탐색은 상하좌우로만 가능하다.

2. 경로를 찾는데 높이가 지금보다 낮은 쪽으로만 이동 가능한 경로를 찾는다.

3. 가능한 경로의 개수를 찾는다.

4. dfs 파라메터로 좌표 정보를 넘겨준다. 

 

<코드 구현 : DFS>

import java.util.*;

/*
[백준] 1520번 - 내리막 길 (Java)
*/

public class Main {
    int N, M;
    int A[][];
    boolean visited[][];

    void InputData() {
        Scanner in = new Scanner(System.in);
        M = in.nextInt();
        N = in.nextInt();
        A = new int[M][N];
        for (int i=0; i<M; i++) {
            for (int j=0; j<N; j++) {
                A[i][j] = in.nextInt();
            }
        }
    }

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    void DFS(int x, int y) {
        if (x == M-1 && y == N-1) {
            visited = new boolean[M][N];//다음 탐색을 위해 방문배열 초기화
            count++;
            return;
        }

        visited[x][y] = true;

        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
            if (A[nx][ny] >= A[x][y]) continue;
            if (visited[nx][ny]) continue;
            DFS(nx, ny);
        }
    }

    int count = 0;
    void Solve() {
        visited = new boolean[M][N];
        DFS(0, 0);
        System.out.println(count);
    }

    void printMap() {
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                System.out.print(A[i][j]+" ");
            }
            System.out.println();
        }
    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<제출 결과 - 메모리초과>

 

<풀이 분석>

1. 경로 탐색 시 지금 높이보다 낮은 쪽으로만 이동이 가능하므로 방문배열을 필요가 없다.

2. 방분배열을 삭제해서 메모리 사용량을 줄이자.

 

<제출 결과 - 시간 초과>

 

<풀이 분석>

1. DFS가 재귀호출이다보니까 M, N이 500이하의 자연수이므로 시간초과가 난다.

2. 따라서 중복호출을 최대한 줄여야 하기에 DP 테이블을 사용하자.

  2-1. DP[x][y]에 저장하는 값은 (x, y)에서 도착점까지 가는 경로의 수이다.

  2-2. 만약 탐색해 가다가 (x, y)까지 도착하면 계속 탐색하는 것이 아니라 DP[x][y] 값을 재사용하면 연산횟수를 줄일 수 있다.

 

<코드 구현 : DFS + DP>

import java.util.*;

/*
[백준] 1520번 - 내리막 길 (Java)
*/

public class Main {
    int N, M;
    int A[][];
    int DP[][]; //메모제이션용

    void InputData() {
        Scanner in = new Scanner(System.in);
        M = in.nextInt();
        N = in.nextInt();
        A = new int[M][N];       
        for (int i=0; i<M; i++) {
            for (int j=0; j<N; j++) {
                A[i][j] = in.nextInt();
            }
        }
    }

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    int DFS(int x, int y) {
        if (x == M-1 && y == N-1) {
            return 1; //도착점에 도달하면 일단 경로의 수 +1을 득한다.
        }
        
        if (DP[x][y] != -1) { //DP에 저장된 값이 있으면 그 값을 재사용한다.
            return DP[x][y];
        }

        DP[x][y] = 0; //현재 위치에서 끝점까지 가는 경로의 수를 0으로 초기화

        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
            if (A[nx][ny] >= A[x][y]) continue;
            DP[x][y] += DFS(nx, ny); //DP[x][y]까지 값에 DFS(nx, ny)의 경로의 수를 누적합한다.
        }
        return DP[x][y];
    }

    int count = 0;
    void Solve() {
        DP = new int[M][N]; //(x,y)에서 도착점까지 가는 경로의 수
        for (int i=0; i<M; i++) {
            for (int j=0; j<N; j++) {
                DP[i][j] = -1;
            }
        }
        int ans = DFS(0, 0);
        //printDP();
        System.out.println(ans);

    }

    void printDP() {
        for (int i=0; i<M; i++) {
            for (int j=0; j<N; j++) {
                System.out.print(DP[i][j]+" ");
            }
            System.out.println();
        }
    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

<제출 결과>