[프로그래머스] #lv.3 - 등굣길 (Java)

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

프로그래머스

 

# 힌트

생각보다 쉬운 최단경로 경우의 수 구하는 문제이다. 근데 함정은 이 문제 자체에 있다... 좋은 문제는 아닌 것 같다.

물 웅덩이의 좌표는 x, y가 거꾸로 되어있으니 주의하자. (2,2) 이렇게 되어있어서 심지어 헷갈린다. 

본인이 코드를 제대로 작성한 것 같은데 테스트케이스 1개만 성공한다면 웅덩이 좌표를 확인하길 바란다.

 

효율성 테스트 힌트 : 이것도 좀 문제가 이상한데, 경우의 수를 더할 때 계속해서 큰 수로 나눈 나머지를 넣어주면 된다.

 

해답 보기

    public static int solution(int m, int n, int[][] puddles) {
        int[][] d = new int[n][m];
        for (int[] puddle : puddles)
            d[puddle[1] - 1][puddle[0] - 1] = -1;

        d[0][0] = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (d[i][j] == -1 || (i == 0 && j == 0)) continue;
                int next;
                // 맨 위 라인
                if (i == 0) {
                    if (d[0][j-1] == -1) next = 0;
                    else next = d[0][j-1];
                } // 맨 왼쪽 라인
                else if (j == 0) {
                    if (d[i-1][0] == -1) next = 0;
                    else next = d[i-1][0];
                }
                else {
                    int fromLeft = d[i][j-1];
                    int fromTop = d[i-1][j];
                    // 왼쪽이 물 웅덩이 -> 위에서 오는거 선택
                    if (fromLeft == -1) next = fromTop;
                    // 위쪽이 물 웅덩이 -> 왼쪽에서 오는거 선택
                    else if (fromTop == -1) next = fromLeft;
                    else next = (fromLeft + fromTop) % 1_000_000_007; // 효율성 테스트 넘기기
                }
                d[i][j] += next;
            }
        }
        int answer = d[n - 1][m - 1];
        return answer % 1_000_000_007;
    }