[Lv.3] 프로그래머스 - 등굣길 : Java

프로그래머스

 

 

 

이해하기

일단 이 문제... 행과 열이 반대다.

m이 열, n이 행을 나타내고 그림 또한 반대로 생각해야 한다.

 

 

 

 

 

 

 

예시를 이렇게 바꿔서 봐야 풀 수 있다...

이걸 첨엔 몰랐어서 뭐지 싶었던 ㅜㅅㅜ

 

 

 

 

 

 

 

 

참고한 블로그⬇️

[프로그래머스] 등굣길 - JAVA

 

 

 

 

 

 

시작점인 (1, 1)은 1을 넣어주고,

웅덩이를 구분하기 위해 -1을 넣어준다.

 

우리가 구해야하는 값은 빨간색까지의 최단거리이며

우리는 오른쪽과 아래쪽으로만 이동할 수 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(2, 1), (3, 1)까지 갈 수 있는 방법은 시작점으로부터 오른쪽으로 이동하는 방법 1가지뿐이니 둘 다 1로 채운다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(1, 1), (1, 2), (1, 3), (1, 4)도 마찬가지로 아래쪽으로 이동하는 방법 1가지 뿐이니 전부 1로 채운다.

 

 

 

 

 

 

 

 

 

나머지 부분은 왼쪽에서 해당 칸으로 올 수 있는 방법 (오른쪽 이동)의 개수와 위쪽에서 해당 칸으로 올 수 있는 방법 (아래쪽 이동) 개수를 더해주면 된다.

단, -1은 웅덩이니 따로 계산하지 말고 0으로 바꾼 후 넘어간다.

 

 

 

 

 

 

 

 

 

빨간색 칸 (학교) 로 가는 최단 거리는4가 된다!

 

 

 

 

 

 

 

 

다른 블로그를 보니 초딩 때 배운 최단 거리 구하는 방식이라는데 나는 왜 기억이 안 나는지...?

 

 

문제풀이

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] road = new int[n][m];

        for (int i = 0; i < puddles.length; i++) {
            road[puddles[i][1] - 1][puddles[i][0] - 1] = -1;
        }
        
        road[0][0] = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (road[i][j] == -1) {
                    road[i][j] = 0;
                    continue;
                }
                
                if (i != 0) {
                    road[i][j] += road[i - 1][j] % 1000000007;
                }
                
                if (j != 0) {
                    road[i][j] += road[i][j - 1] % 1000000007;
                }
            }
        }
        
        return road[n - 1][m - 1] % 1000000007;
    }
}