🍊문제

프로그래머스 : 등굣깃

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.
가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

입출력 예

m : 4
n : 3
puddles : [[2, 2]]
return : 4

🍊풀이

초기 접근

처음에는 최소 경로를 구하는 문제니까 bfs로 풀어야하나..? 했다.
근데 문제의 요구사항이 '최소경로'가 아니라 '최단경로의 개수'이기 때문에, 경로의 수를 누적해서 계산하는 DP로 풀어야 함음 알았다.

문제 분석

이 문제는 다른 dp 문제와 다른 점이 몇 가지 있다.

1. 장애물 '우물'💦

중간에 지나갈 수 없는 길인 '우물'이 존재한다. 따라서 경로의 수를 구할 때, 해당 우물을 지나가는 경로는 카운트하지 않도록 처리한다.

2. 오른쪽과 아래쪽으로만 움직일 수 있다.

보통은 4방향 탐색, 8방향 탐색이 일반적이지만 이 문제는 오른쪽과 아래쪽으로만 이동할 수 있다.
그러므로, 현재위치까지의 경로의 수는 현재위치에서 한칸 왼쪽의 경로의 수 + 현재위치에서 한칸 위쪽의 경로수가 된다.

3. 출력요구

"최단경로의 개수를 1,000,000,007로 나눈 나머지를 return해야 한다."

자칫하면 이 과정에서 범위 초과가 날 수 있으니 이 부분을 잘 고려해야 한다.

풀이 과정

1. MOD 변수 생성, dp 배열 생성

		//return할 때 필요한 변수 생성
        int MOD = 1_000_000_007;
        
        //집까지 갈 수 있는 경로의 수를 저장하는 dp배열 만들기
        //도착지점이 (m, n)이기 때문에 범위를 +1씩 지정하기
        int[][] dp = new int[n+1][m+1];
      

2. 우물이 있는 곳 표시

  
        //우물이 있는 곳은 경로를 계산할 수 없으므로 -1로 채우기
        for (int i = 0 ; i < puddles.length; i++) {
            int x = puddles[i][0];
            int y = puddles[i][1];
            
            dp[y][x] = -1; //인덱스 순서 주의! [x][y]로 하면 틀림
        }

🚨여기서 주의할 점
문제에서 위치 표시를 2차원 격자 위에 표시하고 있는데, 이는 코딩할 때 2차원 배열과의 x, y 좌료가 반대이기 때문에 이 부분을 조심하도록 하자

빨간색 부분은 2차원 배열에서는 [1, 2]로 나타내지만 문제에서는 [2, 1] 같이 반대로 나타내기 때문에 조심할 것

3. 배열을 돌면서 경로의 수 탐색하기

        //시작지점은 경로의 개수가 1이므로 1로 처리
        dp[1][1] = 1;
        
        //2차원 배열 돌기
        for (int i = 1;  i < n +1; i++) {
            for (int j = 1; j < m + 1; j++) {
                //시작지점이라면 넘어가기
                if (i == 1 && j == 1) continue;
                //우물을 만났다면 넘어가기
                if (dp[i][j] == -1) continue;
            
                int down_path = dp[i - 1][j];
                int right_path = dp[i][j-1];
                
                //우물을 만났을 때의 처리방식
                if (down_path == -1) {
                    down_path = 0;
                } else if (right_path == -1){
                    right_path = 0;
                }
                
                //현재 위치의 경로의 수는 왼쪽 경로의 수 + 위쪽 경로의 수 
                dp[i][j] = (down_path + right_path) % MOD;
            }
        }

⭐️중요한 지점
문제에서 도착지점의 경로의 수에서 1_000_000_007을 나눈 나머지를 출력하라고 했다.
만약 dp 배열을 다 돌고 도착지점에서 MOD를 나누면 int 범위를 벗어날 수 있기 때문에 매 경로를 구할 때마다 MOD를 나누어 저장해주는 게 안전하다.

4. return 하기

도착지점의 dp의 값을 return 하면 최단경로의 개수를 구할 수 있다!

        answer = dp[n][m];
        
        
        return answer;

🍊전체코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int MOD = 1_000_000_007;
        
        //오른쪽과 아래쪽으로만 움직일 수 있다.
        //집까지 갈 수 있는 경로의 수를 저장하는 dp배열 만들기
        int[][] dp = new int[n+1][m+1];
        //우물이 있는 곳은 경로를 계산할 수 없으므로 -1로 채우기
        for (int i = 0 ; i < puddles.length; i++) {
            int x = puddles[i][0];
            int y = puddles[i][1];
            
            dp[y][x] = -1; //인덱스 순서 주의! [x][y]로 하면 틀림
        }
        //첫번째 경로 1처리
        dp[1][1] = 1;
        
        //현재까지의 경로의 수는, 왼쪽 경로 수의 + 1, 위의 경로 수의 +1 이다.
        for (int i = 1;  i < n +1; i++) {
            for (int j = 1; j < m + 1; j++) {
                //시작지점이라면 넘어가기
                if (i == 1 && j == 1) continue;
                //우물을 만났다면 넘어가기
                if (dp[i][j] == -1) continue;
            
                int down_path = dp[i - 1][j];
                int right_path = dp[i][j-1];
                //우물을 만났을 때의 처리방식
                if (down_path == -1) {
                    down_path = 0;
                } else if (right_path == -1){
                    right_path = 0;
                }
                
                dp[i][j] = (down_path + right_path) % MOD;
            }
        }
        answer = dp[n][m];
        
        
        return answer;
    }
}