[programmers] 등굣길 - Java

등굣길

문제 설명

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
• m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.

• 물에 잠긴 지역은 0개 이상 10개 이하입니다.

• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

입출력 예 설명

solution.java

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        // 상수 정의
        final int MOD = 1_000_000_007;

        // 격자 초기화
        int[][] dp = new int[m + 1][n + 1];

        // 물에 잠긴 지역을 -1로 표시
        for (int[] puddle : puddles) {
            dp[puddle[0]][puddle[1]] = -1;
        }
        
        // (1,1)부터 격자 시작 
        dp[1][1] = 1;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 시작 셀과 물에 잠긴 지역 건너뛰기
                if ((i == 1 && j == 1) || dp[i][j] == -1) continue;

                // 현재 셀에 대한 방법 수 계산
                int fromAbove = (i > 1 && dp[i - 1][j] != -1) ? dp[i - 1][j] : 0;
                int fromLeft = (j > 1 && dp[i][j - 1] != -1) ? dp[i][j - 1] : 0;

                dp[i][j] = (fromAbove + fromLeft) % MOD;
                System.out.println("dp["+i+"]["+j+"] = "+dp[i][j]);
            }
        }

        // 결과는 격자의 오른쪽 하단 모서리에 있는 값
        return dp[m][n];
    }
}

핵심 키워드

• 오른쪽과 아래쪽으로만 움직일 수 있으므로 좌측 셀에서의 가능한 경로 개수와 위쪽 셀에서의 가능한 경로 개수를 합치면 현재 셀의 경로 개수를 구할 수 있다.

• 이 경우 시간복잡도는 각 셀을 한번씩 반복하므로 다음과 같다.

결론!