[Programmers] 등굣길 - 동적계획법(Dynamic Programming)

// 등굣길 - 동적계획법(Dynamic Programming)
public class SchoolLoad { // 최단거리로 이동해야 함 (전제조건)

	public int solution(int m, int n, int[][] puddles) {

		int[][] dp = new int[n + 1][m + 1];
		for (int[] puddle : puddles) {	// 물웅덩이를 -1로 저장
			dp[puddle[1]][puddle[0]] = -1;
		}
		dp[1][1] = 1; // 초기값을 지정해주어야 함

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (dp[i][j] == -1) {
					continue;
				} else if (i == 1 && j > 1) {
					dp[i][j] = dp[i][j - 1];
				} else if (j == 1 && i > 1) {
					dp[i][j] = dp[i - 1][j];
				} else if (i != 1 && j != 1) {
					if (dp[i - 1][j] == -1 && dp[i][j - 1] == -1) { // 도착지점에 아예 도착하지 못할 상황이 있음. 위아래로 물웅덩이 존재 시
						dp[i][j] = 0;
					} else if (dp[i - 1][j] == -1) {	// 위에 물웅덩이
						dp[i][j] = dp[i][j - 1];
					} else if (dp[i][j - 1] == -1) {	// 왼쪽에 물웅덩이
						dp[i][j] = dp[i - 1][j];
					} else {
						dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007;
					}
				}
			}
		}
		return dp[n][m];
	}

}