[프로그래머스] 등굣길

programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

문제 설명 : 

m X n 크기의 격자모양에서 집이 있는 좌표는 (1,1)이고 학교가 있는 좌표는 (m,n) 입니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단 경로의 개수를 1,000,000,007로 나눈 나머지를 출력하기

 

문제 풀이 : 

2차원 배열 map을 만들어서 puddles 좌표(물 웅덩이를) 위치를 -1로 초기화 해둡니다.

집이 있는 좌표는 1로 두고, 물 웅덩이 위치를 다시 0으로 만든 후,

오른쪽과 아래쪽으로만 움직이기 때문에 왼쪽과 위쪽을 확인해서 더해가면 됩니다.

class Solution {
    public static int solution(int m, int n, int[][] puddles) {
        int[][] map = new int[n+1][m+1];
        
        for (int i = 0; i < puddles.length; i++) {
			for (int j = 0; j < 2; j++) {
				int x = puddles[i][1];
				int y = puddles[i][0];
				map[x][y] = -1;//물 웅덩이를 -1로 둔다
			}
		}
        map[1][1] = 1;//집이 있는 좌표

        for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				 if (map[i][j] == -1) map[i][j] = 0;//물 웅덩이는 0으로 계산한다.
		         //왼쪽, 위를 확인하면서 더해준다.
				 else map[i][j] += (map[i-1][j] + map[i][j-1]) % 1000000007;

			}
		}
        return map[n][m] % 1000000007;
    }
}