문제

문제 바로가기

풀이

위 예시의 각 좌표까지 도달할 수 있는 최단경로의 개수를 나타내면 아래와 같다.

감이 잡힐 것이다!
어떤 한 좌표까지 도달할 수 있는 최단경로의 개수는 해당 좌표의 왼쪽 좌표까지의 최단경로 수 + 해당 좌표의 위쪽 좌표까지의 최단경로 수이다.

DP 풀이

Top-Down 방식

우선 처음으로 생각이 났던 것은 백트래킹이었으나, DP로 풀어보고 싶어서 DP로 풀이를 작성했다.
학교 좌표가 특이하게 (n,m)이 아니라 (m,n)이라고 문제에서 명시하고 있다.
따라서 puddles로 들어오는 물에 잠긴 지역의 좌표를 그대로 사용하지 말고 처리를 해주어야 한다.

class Solution {
    static int[][] dp;
    static int N, M;
    static public int solution(int m, int n, int[][] puddles) {
        N = n;
        M = m;
        dp = new int[n][m]; // 문제 조건에 의해 puddles의 좌표에 -1씩 해주어야 함. 두 좌표를 서로 바꿔줘야 함.
        for(int i=0; i<puddles.length; i++) {
            dp[puddles[i][1]-1][puddles[i][0]-1] = -1;
        }
        dp[0][0] = 1;
        return dfs(n-1,m-1);
    }
    
    static public int dfs(int row, int col) {
        // 범위 밖, 혹은 물에 잠긴 지역
        if(row < 0 || col < 0 || row > N || col > M || dp[row][col] < 0 ) return 0; 
        if(dp[row][col] > 0) return dp[row][col];
        dp[row][col] = dfs(row,col-1) +  dfs(row-1,col);
        return dp[row][col];
    }
}

그러나 이 풀이는 효율성 테스트에서 전멸을 해버렸다 .. 흑흑
손으로 직접 경로를 따라가봐도 불필요한 방문은 하지 않는 코드인데 여기서 얼마나 더 효율적으로 짜라는건지 감이 잘 안 잡혔다.

Bottom-Up 방식

내가 미처 알지 못 하는 컴파일러 내부에서의 사소한 차이때문에 효율성 테스트를 통과하지 못 하는걸까? 싶어서 일단 Bottom-Up 방식으로 한 번 더 짜봤다.

문제에서 제시한 대로 현재 좌표의 오른쪽과 아래쪽에 현재까지의 최단 경로 수를 더해준다.

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n][m]; // 문제 조건에 의해 puddles의 좌표에 -1씩 해주어야 함. 두 좌표를 서로 바꿔줘야 함.
        
        for(int i=0; i<puddles.length; i++) {
            dp[puddles[i][1]-1][puddles[i][0]-1] = -1;
        }
        
        dp[0][0] = 1;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(dp[i][j]<0) continue;
                if(i+1 < n && dp[i+1][j] >= 0) {
                    dp[i+1][j] += dp[i][j];    
                }
                if(j+1 < m && dp[i][j+1] >= 0) {
                    dp[i][j+1] += dp[i][j];     
                }
            }
        }
        
        return dp[n-1][m-1];
    }
}

아니 근데도 효율성 테스트에서 전멸을 하는 거다 ..
여기서 이상한 점을 깨닫고 문제를 다시 살펴봤다.

...

😇🔫

최종 제출 코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n][m]; // 문제 조건에 의해 puddles의 좌표에 -1씩 해주어야 함. 두 좌표를 서로 바꿔줘야 함.
        
        for(int i=0; i<puddles.length; i++) {
            dp[puddles[i][1]-1][puddles[i][0]-1] = -1;
        }
        
        dp[0][0] = 1;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(dp[i][j]<0) continue;
                if(i+1 < n && dp[i+1][j] >= 0) {
                    dp[i+1][j] += (dp[i][j]%1000000007) ;    
                }
                if(j+1 < m && dp[i][j+1] >= 0) {
                    dp[i][j+1] += (dp[i][j]%1000000007);     
                }
            }
        }
        
        return dp[n-1][m-1] % 1000000007;
    }
}

...

(+번외)

Top-Down 방식도 나머지 연산 처리를 해주니 효율성 테스트에서 모두 통과하였다.

class Solution {
    static int[][] dp;
    static int N, M;
    static public int solution(int m, int n, int[][] puddles) {
        N = n;
        M = m;
        dp = new int[n][m]; // 문제 조건에 의해 puddles의 좌표에 -1씩 해주어야 함. 두 좌표를 서로 바꿔줘야 함.
        for(int i=0; i<puddles.length; i++) {
            dp[puddles[i][1]-1][puddles[i][0]-1] = -1;
        }
        dp[0][0] = 1;
        return dfs(n-1,m-1);
    }
    
    static public int dfs(int row, int col) {
        // 범위 밖, 혹은 물에 잠긴 지역
        if(row < 0 || col < 0 || row > N || col > M || dp[row][col] < 0 ) return 0; 
        if(dp[row][col] > 0) return dp[row][col];
        dp[row][col] = dfs(row,col-1)%1000000007 +  dfs(row-1,col)%1000000007;
        return dp[row][col]%1000000007; 
    }
}

---

정신 차리자