[백준] 1520 : 내리막길

문제 출처: https://www.acmicpc.net/problem/1520

소요 시간 : 시도(30m) + 풀이(???)

---

문제

 

 

 

---

시도

 

처음엔 단순하게 시작점(0, 0)에서 종착점(N, M)으로 갈 수 있는 경우의 수만 따지면 되겠지 생각하고 가볍게 여겼는데, 2가지에서 난항을 겪었다.

 

첫째는 기존 수보다 낮은 값을 지닌 칸으로만 이동할 수 있다는 점,

그리고 둘째는 이동이 좌 → 우, 상 → 하 뿐만 아니라 조건만 만족한다면 우 → 좌 로의 이동까지 가능해야 한다는 점이다.

 

문제에선 예시를 매우 순탄한 걸로 줘서 괜찮을 수도 있지만 극단적으로 다음과 같이 지도가 주어진다면 어떻게 대처해야 할지 고민했다.

 

3 2 1 1 2

3 2 1 2 3

2 2 1 1 1

 

이런 극단적인 지도가 주어진다면 어떻게 처리해야 할지 골몰했지만 결국 코드 한 줄도 짜지 못했다.

 

여기까지 걸린 시간이 30분

---

풀이

 

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

public class Main {

	private static int m, n;
    
    private static int[][] map;
    private static int[][] dp;
    
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};

	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        
        map = new int[m+1][n+1];
        dp = new int[m+1][n+1];
        
        for (int i = 1; i <= m; i++) {
        	st = new StringTokenizer(br.readLine());
            
            for (int j = 1; j <= n; j++) {
            	map[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }
        
        System.out.print(dfs(1,1));
    }
    
    private static int dfs(int x, int y) {
    	if (x == m && y == n) {
        	return 1;	// 도달했을 때 추가탐색 필요 없다.
        }
        
        if (dp[x][y] != -1) {
        	// -1이 아닌 경우 이미 방문했다.(메모이제이션)
            return dp[x][y];
        }
        
        // -1인 경우
        dp[x][y] = 0;
        for (int i = 0; i < dx.length; i++) {
        	int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx < 1 || ny < 1 || nx > m || ny > n) {
            	continue;
            }
            
            if (map[x][y] > map[nx][ny]) {
            	// 현재 값이 더 큰 경우
                dp[x][y] += dfs(nx, ny);
            }
        }
        
        return dp[x][y];
    }
}

 

참조 링크 : https://hidelookit.tistory.com/171

---

알게 된 점

 

DP 뿐만 아니라 DFS까지 적용해야 했던 문제였다...