[동적계획법] 등굣길

|| 문제설명 ||

1. 계속되는 폭우로 일부 지역이 물에 잠겼다.
2. 물에 잠기지 않은 지역을 통해 학교를 가려고 한다.
   • 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있다.
   • 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)
   • 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)
3. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성하라.

• int m, n : 격자의 크기
• int[][] puddles : 물이 잠긴 지역의 좌표를 담은 2차원 배열

---

|| 문제해결방법 ||

- 이때 puddles도 아래와 같이 주어진다.
	puddles[i][0] : x축
   	puddles[i][1] : y축

---

|| 코드 ||

[2021.01.26] 실패

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] map = new int[n+1][m+1];

        for(int i = 0 ; i < puddles.length; i++) 	// 장애물 설치
            map[puddles[i][1]][puddles[i][0]] = -1;
        
        map[0][1] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                map[i][j] = (map[i][j] == -1) ? 0 : map[i-1][j] + map[i][j-1];
            }
        }
        return map[n][m]%1000000007;
    }
}

---

[2021.01.26]

효율성 테스트에서 딱걸린 이유

- 예외 : input의 단위가 매우 클 경우 
더해지는 값(map[i-1][j] + map[i][j-1])이 1,000,000,007보다 커질 수 있기 때문에 매번 나머지를 구해서 더해줘야한다.

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] map = new int[n+1][m+1];

        for(int i = 0 ; i < puddles.length; i++) 	// 장애물 설치
            map[puddles[i][1]][puddles[i][0]] = -1;
        
        map[0][1] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                map[i][j] = (map[i][j] == -1) ? 0 : (map[i-1][j] + map[i][j-1])%1000000007;
            }
        }
        return map[n][m]%1000000007;
    }
}