[알고리즘] 프로그래머스 등굣길 -DP- 자바

 

 

programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

 

 

프로그래머스 LV3 동적계획법(DP) 문제 등굣길을 풀어봤습니다.

 

집에서 학교까지 웅덩이를 피해 갈 수 있는 모든 최단 경로의 수를 구하면 되는 문제였습니다.

 

집은 1,1  학교는 n,m 에 있고 최단 거리만 계산하면 되므로 상하좌우가 아닌 우측과 하단으로 이동만 하면 됩니다.

row와 col 인덱스로 이루어진 이중 배열을 만들고 값으로는 해당 지점까지 오는데까지의 경로의 수를 저장하며 DP 로 풀이했습니다.

그리고 빗물이 있는데 이를 3중 배열로 표현할까 했다가 이중배열에서 값을 -1일때는 빗물로 취급하게 했습니다.

 

풀이는 다음과 같습니다.

 

[Java]

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        // (1,1 부터 시작이여서 덜 햇갈리개 +1해서 배열크기 생성함)
        int[][] dp = new int[n + 1][m + 1]; // [Row, Col] = 경우의 수(이떄 -1은 웅덩이로 취급)
        for (int i = 0; i < puddles.length; i++) {
            dp[puddles[i][1]][puddles[i][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 (j - 1 > 0 && dp[i][j - 1] != -1) dp[i][j] += dp[i][j - 1] % 1000000007; //하단 이동
                if (i - 1 > 0 && dp[i - 1][j] != -1) dp[i][j] += dp[i - 1][j] % 1000000007; //우측 이동
            }
        }
        return dp[n][m] % 1000000007;
    }
}

 

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!