등굣길

등굣길

🙋‍♂️ 들어가며

이번 문제는 경로의 수를 구하는 문제로 예외처리가 중요한 문제였다.

처음에 back_tracking으로 재귀호출을 생각해보았는데 역시 되지 않겠다

why?

총 이동 횟수는

N = (m-1) + (n-1)

이때 경로의 갯수

N C (m-1)

198 C 99

약 9 * 10^58

그래서 back_tracking 불가능

그러면 DP로 풀어보자

테두리를 먼저 계산해주고 한 좌표를 기준으로 왼쪽, 위쪽을 구해야하는데

이때 왼쪽이나 위쪽이 웅덩이가 있다면 계산할때 0으로 처리하여 구해야했다

아래가 좋은 예시다

예시

1	0	-1	0
0	0	0	0
-1	0	0	0

->

1	1	-1	-1
1	2	2	2
-1	2	4	6

이렇게 된 이유는 다음 조건이 있기 때문이다

• 우측 or 아래로만 지나갈 수 있다.
  
  

✅ 코드

class Solution {
    static int row, col;
    static int[][] DP;
    static int er, ec;
    static int mod = 1000000007;
    
    public int solution(int m, int n, int[][] puddles) {
        row = n;
        col = m;
        DP = new int[row][col];
        
        // 1. 초기값
        DP[0][0] = 1;
        er = row-1;
        ec = col-1;
        
        // 2. puddles 채우기
        for (int[] pu : puddles) {
            int r = pu[1]-1;
            int c = pu[0]-1;
            DP[r][c] = -1;
        }
        
        // 2. 우측 테두리 채우기
        for (int c = 1; c < col; c++) {
            if (DP[0][c] == -1) continue;
            DP[0][c] = DP[0][c-1];
        }
        
        // 3. 아래 테두리 채우기
        for (int r = 1; r < row; r++) {
            if (DP[r][0] == -1) continue;
            DP[r][0] = DP[r-1][0];
        }
        
        // 4. 탐색
        for (int r = 1; r < row; r++) {
            for (int c = 1; c < col; c++) {
                // 4-1. 연못이면 skip
                if (DP[r][c] == -1) continue;
                // 4-2. 그렇지 않다면
                else if (DP[r][c] != -1) {
                    int up = DP[r-1][c];
                    int left = DP[r][c-1];
                    if (DP[r-1][c] == -1) up = 0;
                    if (DP[r][c-1] == -1) left = 0;
                    
                    DP[r][c] = (up + left) % mod;
                }
            }
        }
        
        
        return DP[er][ec];
    }
}