[프로그래머스] 등굣길(Java)

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

프로그래머스

---

문제 풀이

물웅덩이가 있는 곳을 피해 최단거리를 구해야 한다.

갈 수 있는 방향은 왼->오 & 위->아래 뿐이므로 기본 점화식을 세우면 아래와 같다.

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

 

 

 

위의 점화식을 사용해 코드를 작성하였지만, 효율성 문제에서 실패하였다.

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n+1][m+1];
        
        // 점화식
        // dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        // 물웅덩이 -1 처리
        for(int[] puddle : puddles) {
            dp[puddle[1]][puddle[0]] = -1;
        }
        
        dp[1][1] = 1;
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                
                // 물웅덩이 스킵
                if(dp[i][j] == -1) {
                    continue;
                }
                
                // 왼쪽 옆칸이 물웅덩이가 아니라면 더해줌
                if(dp[i-1][j] > 0) {
                    dp[i][j] += dp[i-1][j];
                }
                
                // 윗칸이 물웅덩이가 아니라면 더해줌
                if(dp[i][j-1] > 0) {
                    dp[i][j] += dp[i][j-1];
                }
            }
        }
        return dp[n][m];
    }
}

 

 

 

실행 결과

 

 

 

효율성 체크를 위해 1000000007로 나눠주어야 한다..

 

아래와 같이 배열에 값을 넣을 때 % 1000000007 계산 후 통과하는 것을 확인하였다.

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n+1][m+1];
        
        // 점화식
        // dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        // 물웅덩이 -1 처리
        for(int[] puddle : puddles) {
            dp[puddle[1]][puddle[0]] = -1;
        }
        
        dp[1][1] = 1;
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                
                // 물웅덩이 스킵
                if(dp[i][j] == -1) {
                    continue;
                }
                
                // 왼쪽 옆칸이 물웅덩이가 아니라면 더해줌
                if(dp[i-1][j] > 0) {
                    dp[i][j] += dp[i-1][j] % 1000000007;
                }
                
                // 윗칸이 물웅덩이가 아니라면 더해줌
                if(dp[i][j-1] > 0) {
                    dp[i][j] += dp[i][j-1] % 1000000007;
                }
            }
        }
        return dp[n][m] % 1000000007;       
    }
}