https://programmers.co.kr/learn/courses/30/lessons/42898
등굣길 경로의 경우의 수를 구하는 문제이다.
좌표 (1,1)인 집에서 부터 (m,n)인 학교까지 가는 경로를 구하는 문제인데 사이에 웅덩이를 피해 가야한다.
puddles[[2,2]]와 같이 2차원 배열로 웅덩이 좌표가 m, n과 같이 입력된다.
2차원 배열에서 최단 거리를 구하는 방법은 다음과 같다.
-> DP
public class Main
{
public static int func(int m, int n, int[][] puddles)
{
int[][] street = new int [n][m]; // m을 열, n을 행
street[0][0] = 1;
for (int i=0; i<puddles.length; i++) // 웅덩이 있는 곳을 -1로 표시
street[puddles[i][1]-1][puddles[i][0]-1] = -1;
for (int i=0; i<n; i++)
{
for (int j=0; j<m; j++)
{
if (street[i][j] == -1)
{ // 웅덩이 만날 경우
street[i][j] = 0;
continue; // 0으로 바꾸고 continue.
// 0에서 더 더하면 안됨
}
if (i != 0) // 첫 행 아니면 위에 값 더함
street[i][j] += street[i-1][j];
if (j != 0) //첫 열 아니면 왼쪽 값 더함
street[i][j] += street[i][j-1];
}
}
for (int i=0; i<n; i++)
{
for (int j=0; j<m; j++)
{
System.out.print(street[i][j] + " ");
}
System.out.println();
}
return street[n-1][m-1];
}
public static void main(String[] args)
{
int m = 6, n = 4; // 열과 행
int[][] puddles = {{2,2}, {4,3}};
func(m, n, puddles);
}
}