[알고리즘_풀이] 프로그래머스 등굣길 java

https://programmers.co.kr/learn/courses/30/lessons/42898#

코딩테스트 연습 - 등굣길 | 프로그래머스

 

생각

(1, 1)부터 (i, j)까지의 최단 경로 개수 .... (1, 1)부터 (m, n) 최단 경로 개수 이렇게 하나씩 채워나가서 답을 구하는 거니까 DP

 

풀이

1. d[i][j]의 정의

   d[i][j] : (1, 1) ~ (i, j) 까지, 웅덩이를 지나지 않고 지나갈 때의 최단 거리의 개수

   결국, i=n, j=m 일 때의 값이 답이다.

2. 웅덩이일 경우 d[][] = -1로 초기화

3. 비교할 땐, 위쪽 방향과 왼쪽 방향만 비교하면 된다.

   1. 현재 있는 곳이 웅덩이인가?

      → 웅덩이라면 넘어가면 됨.

   2. 왼쪽 방향에 있는게 웅덩이 X?

      → 아니면 더한다. (계속 이거 해줘야 효율성 실패 안뜸 %1000000007)

   3. 윗 쪽 방향에 있는게 웅덩이 X?

      → 아니면 더한다. (계속 이거 해줘야 효율성 실패 안뜸 %1000000007)

import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;

class Solution {
    // 위, 아래의 경우만 생각해주면 된다.
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        
        int[][] d = new int[n+1][m+1];
        
        for(int i=0; i<puddles.length; i++) {
            d[puddles[i][1]][puddles[i][0]] = -1;
        }
        
        d[1][1] = 1;
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(d[i][j] == -1) {
                    continue;
                }
                if(d[i][j-1] >= 0 && d[i][j] >= 0) {
                    d[i][j] += d[i][j-1] %1000000007 ;
                }
                if(d[i-1][j] >= 0 && d[i][j] >= 0) {
                    d[i][j] += d[i-1][j] % 1000000007;
                }
            }
        }

        answer = d[n][m]%1000000007;
        
        return answer;
    }
}