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

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

프로그래머스

문제 풀이

런타임 에러가 많이 발생해서 고생했던 문제다. 격자 행렬과 집이 m,n 순서대로 주어지지만 [n,m] 좌표임을 주의하자.

사실 위 부분에서 오류가 발생하진 않았는데 puddle도 m,n으로 주어졌다. 문제에선 2,2를 예시로 줘서 확인하지 못했다. 혹시나 했는데 확인해 보니까 m,n 순서대로 주어지기 때문에 마찬가지로 [n,m]으로 적용해야 한다.

 

map[][]에는 각 좌표에 도착할 수 있는 경로의 경우의 수이다. 먼저 첫 번째 행과, 첫 번째 열은 한 방향으로만 갈 수 있기 때문에 모두 1이다. 이때 주의할 점이 중간에 물 웅덩이가 있다면 그 이후로는 1로 설정하면 안 된다.

다음으로 왼쪽 좌표와 위에 좌표를 합한 값이 해당 좌표의 경우의 수가 될 것이다.

웅덩이를 -1로 구분해놨기 때문에 위에서 합 계산을 할 때 예외처리를 해주어야 한다. 아래 그림에서 [2,3]이 0이 되지 않게 조건문을 걸어주라는 의미이다.

코드

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int[][] maps = new int[n+1][m+1];

        // 웅덩이 추가
        for (int i = 0; i < puddles.length; i++) {
            maps[puddles[i][1]][puddles[i][0]] = -1;
        }

        // 맨 왼쪽 열에 대해 웅덩이가 나오기 전까지 갈 수 있는 경로의 수를 1로
        for (int i = 1; i <= n && maps[i][1] != -1; i++) {
            maps[i][1] = 1;
        }

        // 맨 위 행에 대해 웅덩이가 나오기 전까지 갈 수 있는 경로의 수를 1로
        for (int i = 1; i <= m && maps[1][i] != -1; i++) {
            maps[1][i] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= m; j++) {
                if(maps[i][j]==-1) continue;

                if (maps[i][j - 1] == -1)
                    maps[i][j] = maps[i-1][j];
                else if (maps[i-1][j] == -1)
                    maps[i][j] = maps[i][j-1];
                else
                    maps[i][j] = (maps[i][j-1] + maps[i-1][j])%1000000007;
                
            }
        }

        return maps[n][m];
    }

}