[프로그래머스] 등굣길 Java 풀이 및 해설

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

프로그래머스

 

풀이 방법

이동은 오른쪽 또는 아래로만 이동이 가능하다.

그러면 way[i][j] 위치로 이동하는 최단 경로는 way[i-1][j] 와 way[i][j-1] 위치에서 오는 방법뿐이다.

즉 way[i][j]에 도착하는 최단 경로의 개수는 way[i-1][j] + way[i][j-1]이다.

 

반복문을 통해 x 방향으로 채우고 y 방향으로 채우며

[i][j] 위치의 값을 [i-1][j]와 [i][j-1]의 값 합으로 갱신해주면 된다.

 

갱신할때 우물의 위치를 고려해서 갱신할지말지를 결정해야한다.!

전체 코드

class Solution {
    
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int way[][] = new int[101][101];
        
        for(int i=0; i<puddles.length; i++) {
            way[puddles[i][1]][puddles[i][0]] = -1;
        }
    
        way[1][1] = 1;
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                
                if(way[i][j] == -1)
                    continue;
                
                if(j-1>=0 && way[i][j-1] != -1) {
                    way[i][j] += way[i][j-1];
                    way[i][j] %= 1000000007;
                }
                
                if(i-1>=0 && way[i-1][j] != -1) {
                    way[i][j] += way[i-1][j];
                    way[i][j] %= 1000000007;
                }
            }
        }
        
        answer = way[n][m];
        return answer;
    }
}