문제 - 등굣길

문제 설명

문제 접근

이동하는 방법은 오른쪽과 아래쪽으로만 움직인다. 그래서 bfs를 이용해서 한다면 O(2^(m*n))으로 시간초과가 발생한다.

• 처음 집에 있는 위치에 갈 수 있는 경우의 수는 1이다.

• 집의 아래쪽과 오른쪽으로 갈 수 있는 경우의 수는 각각 1이다.

• 집의 대각선으로 갈 수 있는 경우의 수는 1 + 1 = 2 즉 (1,0)의 값 + (0,1)의 값

• 1,2의 칸으로 갈 수 있는 경우의 수는 그림과 같다. 즉 (1,1) + (0,2) 이다.

위와 같은 방법으로 코드를 구현하면 된다.

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int [][]maps = new int[n][m];
        maps[0][0] = 1;
        
        for(int []p : puddles)
        {
            maps[p[1]-1][p[0]-1] = -1;
        }
        
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(maps[i][j] == 0)
                {
                    //왼쪽
                    if(i != 0 && maps[i-1][j] != -1)
                    {
                        maps[i][j] += maps[i-1][j] ;
                    }
                    //위쪽
                    if(j != 0 && maps[i][j-1] != -1)
                    {
                        maps[i][j] += maps[i][j-1] ;
                    }
                    maps[i][j] %= 1_000_000_007;
                }

            }
        }
        return maps[n-1][m-1];
    }
}