Programmers 등굣길 java 풀이

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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문제와 같이 계산값을 저장하면서 풀면 반복을 줄일 수 있다 라고 생각하고 접근했다. 일단 최단 경로로 이동하기 위해서는 오른쪽으로 가거나, 아래로 가는 선택지만 있다고 보고 각 지점에는 자신까지 올때의 경로의 수를 저장하도록 배열을 만들었다. 여기서 각 지점까지 올 수 있는 경로의 수는 위와 왼쪽 블럭이 막혀있지 않다면 위와 왼쪽 블럭이 가지고 있는 경우의 수를 합한 것으로 구할 수 있었다. 아래 코드로 보면 출발점인 arr[0][0]=1 부터 시작해서 차례로 이동하면서 왼쪽블럭과 위쪽 블럭의 값을 가져와 더한 것. 이번 문제는 DP문제를 몇개 풀어봐서 그런지 생각보다 쉽게 풀려버렸다.

 

코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] arr = new int[n][m];
        arr[0][0] = 1;
        
        for(int[] point : puddles) {
            arr[point[1]-1][point[0]-1] = -1;
        }
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(arr[i][j]<0) continue;
                
                if(i>0 && arr[i-1][j]>0) {
                    arr[i][j] += arr[i-1][j];
                }
                if(j>0 && arr[i][j-1]>0) {
                    arr[i][j] += arr[i][j-1];
                }
                arr[i][j] %= 1000000007;
            }
        }
        
        return arr[n-1][m-1];
    }
}