[백준] 1520번 : 내리막 길

[동적 프로그래밍 + DFS]

1520번: 내리막 길

# 문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

# 입력

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

# 출력

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

# 예제 입력 

4 5

50 45 37 32 30

35 50 40 20 25

30 30 25 17 28

27 24 22 15 10

# 예제 출력 

3

---

문제 자체의 난이도는 어렵지 않은 편이다. 경우의 수를 구하는 것은 DFS나 BFS가지고 금방 구해낼 수 있다. 하지만 시간 초과와 메모리 초과의 늪에 빠져버리면 멘탈이 바스라진다... 다른 분들의 코드를 참고하지 않고는 도저히 시간을 단축 시키는 법을 못찾고 결국 질문들을 보며 코드를 참고했더니... 딱 2줄 정도만 추가했으면 정답이었다 :(

 

DFS + DP로 풀었다면, 시작점 (0,0)에서 출발하여 도착점 (m,n)에 도착하면 1을 반환하여 그 경로에 있는 값들이 1씩 증가되는 매커니즘이다. 단, 각 점이 dp 테이블의 초기값과 다른 값을 가지고 있다면(도착점을 찍는 데에 쓰였던 경로라면) 다른 처리를 하지 않고 바로 값을 반환한다.

 

DFS(int y, int x){

	if(y == m-1 && x == n-1) //도착점에 도착하면 1을 반환
    	return 1;
    
    if(dp[y][x] != 0) //값이 있다면
    	return dp[y][x]; //밑의 Loop을 돌지 않도록
        
    for(int a=0; a<4; a++){
    	int nextY = y + Y[a];
        int nextX = x + X[a];
        
    	if(map[y][x]의 상하좌우 범위 확인 및 다음 칸과 현재 칸의 값 비교)
        	dp[y][x] += DFS(nextY, nextX); //Recursion
    }
    return dp[y][x];
}

이 함수가 내가 짯던 함수이다. 돌고래가 초음파를 보내 물체에 도달하여 다시 돌아오는 것을 생각하면 이해하기 쉬울 것 같다. (0,0)에서 초음파를 보내 (m-1, n-1)에 도달하면 1을 가지고 다시 (0,0)으로 돌아온다.

 

만약 3 X 3 테이블의 값이 아래와 같이 주어진다면.

10	20	5
8	5	3
7	5	1

(10)에서 (1)에 도달하는 경우의 수는 2가지(10-8-7-5-1, 10-8-5-3-1) 이다. DP 테이블로 보면 다음과 같다.

2	0	0
1	1	1
1	1	0

바로 여기서 시간 초과가 발생한다.

 

우리는 갈 수 없는 길과, 한 번도 시도하지 않은 길(DFS에 한번도 호출되지 않은)을 구분해야한다. 갈 수 없는 길은 시작점으로부터 도착점까지의 경로가 중간에 끊긴 길이다. 즉, 갈 수 없는 길은 한 번도 시도하지 않은 길에 둘러 쌓여있을 것이다.

 

* map[][]

50	30	50	10	40
40	20	25	20	30
30	35	28	25	20
15	10	5	4	3
5	4	3	2	1

빨간색이 (도착점으로) 갈 수 없는 길이고, 파란색이 DFS 함수에서 호출될 수 없는 길이다. 이런 길을 구분해주어 메모리와 시간의 낭비를 줄여야 한다. 방법은 DP테이블의 초기화를 -1로 해주는 것이었다.

DFS(int y, int x){

	if(y == m-1 && x == n-1) //도착점에 도착하면 1을 반환
    	return 1;
    
    if(dp[y][x] != -1) //값이 있다면
    	return dp[y][x]; //밑의 Loop을 돌지 않도록
    
    //갈 수 없는 길이라면 0을 계속 유지할 것 이다.
    //만약 DFS에 의해 불려지지 않은 칸은 -1을 유지한다.
    dp[y][x] = 0; 
        
    for(int a=0; a<4; a++){
    	int nextY = y + Y[a];
        int nextX = x + X[a];
        
    	if(map[y][x]의 상하좌우 범위 확인 및 다음 칸과 현재 칸의 값 비교)
        	dp[y][x] += DFS(nextY, nextX); //Recursion
    }
    return dp[y][x];
}

* DP[][]

15	0	-1	0	-1
15	0	0	0	-1
15	10	6	3	1
5	4	3	2	1
1	1	1	1	-1

# Whole Code </>

public class Main {

    static int[][] map;
    static int[][] dp;
    static int[] Y = {1,-1,0,0};
    static int[] X = {0,0,1,-1};
    static int m, n;

    static int DFS(int y, int x){

        if(y == m-1 && x == n-1)
            return 1;

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

        dp[y][x] = 0;

        for(int a=0; a<4; a++){
            int nY = y+Y[a];
            int nX = x+X[a];

            if((nY >= 0 && nY < m) && (nX >= 0 && nX < n) && map[nY][nX] < map[y][x]) {
                dp[y][x] += DFS(nY, nX);
            }
        }
        return dp[y][x];
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        map = new int[m][n];
        dp = new int[m][n];

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }

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

 

# Reference

www.acmicpc.net/board/view/9704