[프로그래머스] 등굣길 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개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

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

입출력 예 설명

문제 풀이

---

문제 풀이는 아래의 그림과 같다

1. map[i][1] = 1로 초기화 시킨다.
2. map[1][i] = 1로 초기화 시킨다.,
3. map[i][j] = map[i-1][j] + ma[i][j-1] 를 하면 아래의 그림과 같이 나타낼 수 있다.

예외 처리

1. map[1][i], map[i][1]에 연못이 있는 경우에는 그 연못부터 끝까지 0처리를 해줘야 한다
2. map[i][j]에 연못이 있는 경우에는 그 부분만 0로 만들어 주면된다!
3. 1_000_000_007을 넘어가는 경우가 있을 수 있기 때문에 map[i][j] = ((map[i-1][j] % DIV ) + (map[i][j-1] % DIV)) % DIV 하면 된다

예시 아래의 그림과 같다.

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        final int DIV = 1_000_000_007;

        // m, n이 주어진다 m : col n : row;

        int[][] map = new int[n + 1][m + 1];

        for (int i = 1 ; i <= n ; i++){
            Arrays.fill(map[i], Integer.MAX_VALUE);
        }

        // 초기화
        for (int i = 1 ; i <= n ; i++) map[i][1] = 1;
        for (int j = 1 ; j <= m ; j++) map[1][j] = 1;



        //puddles m , n
        int row, col;
        for (int[] puddle : puddles){
            col = puddle[0];
            row = puddle[1];

            if (row == 1){
                for (int i = col ; i <= m ; i++){
                    map[row][i] = 0;
                }
            }else if(col == 1){
                for (int i = row ; i <= n ; i++){
                    map[i][col] = 0;
                }
            }else{
                map[row][col] = 0;
            }
        }

        for (int i = 2 ; i <= n ; i++){
            for (int j = 2 ; j <= m ; j++){
                if (map[i][j] == 0) continue;
                map[i][j] = ((map[i - 1][j] % DIV) + (map[i][j - 1] % DIV)) % DIV;
            }
        }


        return map[n][m];
    }
}