[프로그래머스] 등굣길

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

코딩테스트 연습 - 등굣길

문제 설명

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

아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

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

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

 

입출력 예시

풀이

dp[i][j] = i행 j열까지 최단경로의 개수

 

위와 같이 dp[i][j]를 정의하면, 움직이는 것은 오른쪽과 아래쪽으로밖에 못 움직이므로 점화식으로 나타낼 수 있다.

 

(i, j) 까지 오는 방법은 아래 두 가지 밖에 없다.

 

1. 왼쪽 (i, j-1) 에서 오른쪽으로 이동

2. 위쪽(i-1, j) 에서 아래쪽으로 이동

 

따라서, dp[i][j] = dp[i][j-1] + dp[i-1][j] 이다.

 

또한 여기서 중요한 것이, 최단경로를 초기화 하는 것인데..

 

먼저, 물에 잠긴 지역과 집의 경우는 이동할 수 없으므로 dp 배열의 해당 위치에 -1이라는 값을 넣어줬다.

(여기서 puddles 의 좌표가 (행, 열) 이 아니라 (열,행) 형태로 주어져서.. 런타임 에러가 났었다)

 

그리고 집에서 오른쪽으로 가거나, 아래로 가는 경우 최단경로의 개수는 무조건 일직선으로 이동하는 것 1개이다.

다만, 우측 또는 아래로 이동하다가 물에 잠긴 지역을 만날 경우에, 그 이후에 있는 우측 지점들의 경우 최단경로의 개수가 1보다 클 수 있으므로 1로 찍어주는 것을 멈춘다.

 

집에서 오른쪽으로 향하거나, 아래로 향하는 최단경로 개수는 모두 1이다.

이렇게 초기화를 해주면, dp[][] 배열에 값이 채워지지 않은 녀석들, 즉 dp[i][j] = 0 인  녀석들만 위에서 구한 점화식대로 값을 채워주면 된다.

 

dp[i][j] = dp[i][j-1] + dp[i-1][j] 

 

점화식대로 값을 채울 때도, 해당 값들이 물에 잠긴 지역인 경우를 고려해야 한다.

(물에 잠긴 지역일 경우 0으로 처리함)

 

그리고 더해줄 때 int 의 오버플로우 방지를 위해 문제에서 요구한 나머지값을 계산하여 더해준다.

 

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        
        int dp[][] = new int[n][m];

        for(int i=0; i<puddles.length; i++){
            dp[puddles[i][1] -1][puddles[i][0]-1] = -1;
        }
        
        dp[0][0] = -1;
        
        for(int i=0; i<m; i++){
            if(dp[0][i] == -1 && i != 0) break;
            dp[0][i] = 1;
        }
        
        for(int i=0; i<n; i++){
            if(dp[i][0] == -1 && i != 0) break;
            dp[i][0] = 1;
        }
        

        
//         System.out.println(puddles.length);
        
        //System.out.println(puddles[0][0] + " " + puddles[0][1]);
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(dp[i][j] == 0){
                    if(i-1 >=0 && j-1 >= 0){
                        if(dp[i-1][j] != -1 && dp[i][j-1] != -1){
                            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
                        }else if(dp[i-1][j] != -1){
                            dp[i][j] = dp[i-1][j] % 1000000007;
                        }else if(dp[i][j-1] != -1){
                            dp[i][j] = dp[i][j-1] % 1000000007;
                        }
                    }
                }
            }
        }
        
        // for(int i=0; i<n; i++){
        //     for(int j=0; j<m; j++){
        //         System.out.print(dp[i][j] + " ");
        //     }
        //     System.out.println();
        // }
        
        answer = dp[n-1][m-1] % 1000000007;
        
        return answer;
    }
}