[프로그래머스, 42898] 등굣길 (java)

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

728x90

---

메모리: 51.9 MB, 시간: 0.99 ms

사용 알고리즘: 동적계획법（Dynamic Programming）

 

처음 문제를 풀 때는 BFS로 풀었다.

BFS로 사방탐색을 하는 것처럼 이방탐색을 해줬다.(오른쪽, 아래쪽으로만 이동이 가능하니 이방탐색) 정확성 테스트는 모두 통과할 수 있었는데 효율성 테스트는 모두 시간초과가 났다.

 

그래서 다른 방법을 고민해 봤는데, 생각해 보니 오른쪽, 아래쪽으로만 이동이 가능하면 무조건 최단거리일 수밖에 없다.(i, j)로 오는 방법은 (i - 1, j)와 (i, j - 1)에서 오는 방법 밖에 없다.

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

따라서 위의 방정식을 토대로 물 웅덩이로는 지나갈 수 없다는 조건과 1,000,000,007로 나눈 나머지 값을 반환해야 한다는 조건만 신경 써주면 된다.

class Solution {
    
    static final int MOD = 1_000_000_007;
    
    public int solution(int m, int n, int[][] puddles) {
        
        int[][] map = new int[m + 1][n + 1]; // 웅덩이 정보
        int[][] dp = new int[m + 1][n + 1]; // 이동 경로 정보(오른쪽과 아래쪽으로만 이동 가능하므로 항상 최단거리를 보장한다.)
        dp[1][1] = 1;
        
        for(int i = 0; i < puddles.length; i++) { // 웅덩이 정보 map에 저장
            map[puddles[i][0]][puddles[i][1]] = 1;
        }
        
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                // 물 웅덩이면 이동 불가
                if(map[i][j] == 1) continue;
                
                // 위에서 아래쪽으로 내려오는 경우
                if(i - 1 >= 1) dp[i][j] += dp[i - 1][j];
                
                // 왼쪽에서 오른쪽으로 온 경우
                if(j - 1 >= 1) dp[i][j] += dp[i][j - 1];
                
                // 모드 연산
                dp[i][j] %= MOD;
            }
        }
        
        int answer = dp[m][n];
        return answer;
    }
}