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

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

코딩테스트 연습 - 등굣길

 

문제 요약

집(1,1)에서 출발하여 학교(m,n)까지 이동하려 한다. 이동은 오른쪽과 아래로만 제한된다. 물웅덩이 배열이 주어지며 물웅덩이가 있는 위치는 밟을 수가 없다. 학교에 도착하는 경로의 수를 반환하는 함수를 만들어야 한다.

 

문제 풀이

 전형적인 DP 문제이다. 난이도는 어렵지 않고 문제의 핵심은 물웅덩이를 안밟게 하는 부분인 것 같다.

 

내가 푼 방식은 우선 dp 2차원 배열을 만들고 출발점은 1로 초기화하고 물웅덩이는 -1로 초기화한다. 1행부터 하나씩 점화식을 통해 경로의 수를 구할 것인데, 일단 시작점과 웅덩이는 계산하지 않는다. 그리고 왼쪽과 위쪽이 둘다 웅덩이라면 0으로 , 왼쪽만 웅덩이라면 위쪽의 값, 위쪽만 웅덩이라면 왼쪽의 값, 왼쪽과 위쪽이 모두 웅덩이가 아니라면 왼쪽 + 위쪽으로 초기화 해줬다.  

 

나의 코드

class 등굣길 {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[m + 1][n + 1];

        /* 시작점은 1, 웅덩이는 -1 */
        dp[1][1] = 1;
        for (int[] p : puddles)
            dp[p[0]][p[1]] = -1;

        /* dp로 경우의 수 계산 */
        for (int x = 1; x <= m; ++x) {
            for (int y = 1; y <= n; ++y) {
                // 시작점과 웅덩이는 계산하지 않음
                if ((x == 1 && y == 1) || dp[x][y] == -1)
                    continue;
                if (dp[x - 1][y] == -1 && dp[x][y - 1] == -1)
                    continue;
                else if (dp[x - 1][y] == -1)
                    dp[x][y] = dp[x][y - 1];
                else if (dp[x][y - 1] == -1)
                    dp[x][y] = dp[x - 1][y];
                else
                    dp[x][y] = (dp[x - 1][y] + dp[x][y - 1]) % 1000000007;
            }
        }

        return dp[m][n] % 1000000007;
    }
}