Programmers 42898: 등굣길

최단경로를 구하는 것이므로 길을 가는 방법은 오른쪽 또는 아래로 이동하는 방법밖에 없다.

즉, 현재 위치의 가짓수는 현재 위치의 위 또는 왼쪽에서 가능한 가짓수를 더한 값이다. => DP

 

이를 식으로 표현해 보면 DP[i][j] = DP[i-1][j] + DP[i][j-1]이다.

import java.util.*;
class Solution {
	public long solution(int m, int n, int[][] puddles) {
		long mat[][] = new long[n + 1][m + 1];
		for (int i = 1; i < mat.length; i++) {
			Arrays.fill(mat[i], -100);
			mat[i][0] = 0;
		}

		for (int i = 0; i < puddles.length; i++) {
			mat[puddles[i][1]][puddles[i][0]] = -1;
		}

		mat[1][1] = 1;

		findAll(n, m, mat);
		//printMat(mat);

		return mat[n][m];
	}

	public long findAll(int row, int col, long[][] mat) {
		if (mat[row][col] != -100) {
			return mat[row][col];
		}
		long left = findAll(row, col - 1, mat);
		long upper = findAll(row - 1, col, mat);

		if (left == -1 && upper == -1) {
			mat[row][col] = 0;
			return mat[row][col];
		}
		if (left == -1) {
			mat[row][col] = upper;
			return mat[row][col];
		}
		if (upper == -1) {
			mat[row][col] = left;
			return mat[row][col];
		}

		mat[row][col] = (left + upper) % 1000000007;
		return mat[row][col];
	}

	public static void printMat(long[][] mat) {
		for (int i = 0; i < mat.length; i++) {
			for (int j = 0; j < mat[i].length; j++) {
				System.out.print(mat[i][j] + " ");
			}
			System.out.println();
		}
	}
}