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

📌 문제 정보

[Lv3. 등굣길]

💡 접근 방식

이 문제는 목적지까지의 최소 거리를 구하는 것이 아니다! (당연함)
물 웅덩이를 제외한 매 칸까지 도달하는 경우의 수를 누적해서 계산해야 한다.

board[n+1][m+1] 배열을 생성한다.
board[1][1]은 출발점이니 1로 설정하고, 물이 있는 곳은 -1로 둔다.

이동은 오른쪽과 아래로만 가능하다.

• 물이 있는 곳은 continue로 넘김

• 오른쪽으로 이동하는 경우
  board[i][j] += board[i][j-1]

• 아래로 이동하는 경우
  board[i][j] += board[i-1][j]

이렇게 세 가지 경우로 케이스로 나눌 수 있다.

주의해야 하는 것은 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return하는 것인데,
단순히 board[n][m] % 1000000007을 하면 효율성 테스트에서 실패한다.
그래서 값을 누적할 때마다 모듈러 연산을 해주었다.

✅ 코드

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int[][] board = new int[n+1][m+1];
        
        for (int[] water : puddles){
            board[water[1]][water[0]] = -1;
        }
        
        board[1][1] = 1;
        
        for(int i=1; i<=n; i++){
            for (int j=1; j<=m; j++){
                if (board[i][j] == -1){
                    continue;
                }
                
                // 우측 n+1, m
                if (board[i][j-1] > 0){
                    board[i][j] = ( board[i][j] +board[i][j-1]) % 1000000007;
                }
                
                // 아래 n+1, m
                if (board[i-1][j] > 0){
                    board[i][j] =( board[i][j] + board[i-1][j]) % 1000000007;
                }
            }
        }

        
        return board[n][m];
    }
}

🧠 배운 점 & 회고

1. board[n][m] % 1000000007 -> 실패❌
2. board[i][j] += board[i][j-1] % 1000000007 -> 실패❌
3. board[i][j] = (board[i][j] + board[i][j-1]) % 1000000007; -> 성공⭕

1번에서 2번으로 수정했는데도 실패해서, 로직에 문제가 있나 싶었지만
암만 생각해도 없었기에.. 덧셈 후 모듈러 연산을 처리하도록 수정하니 성공할 수 있었다.

🧾 결과