프로그래머스 알고리즘 : 등굣길 (java)

프로그래머스 알고리즘 (java)

등굣길

프로그래머스 (등굣길)

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어질 때, 학교에서 집까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

코드리뷰

조건

• 최단거리를 가야하기 때문에 왼쪽 과 아래 밖에 못 움직인다.
• 웅덩이가 있는곳은 못 지나간다.

풀이방향

이차원 배열을 만들고 웅덩이를 표시하고 거기서부터는 예전 수학시간에 배운 최단거리를 구하는 방법처럼 구해봤습니다. 웅덩이는 -1 로 미리 표시해 두고 최단거리를 구할 때 -1 이 나오면 0 으로 바꾸었 습니다.

만약 m = 4, n = 2 웅덩이가 {2, 2}, {4, 2} 로 주어 진다면, 웅덩이를 표시하고 점을 하나 씩 탐색 해 가면서 점의 위치로 올수 있는 경우의 숫자들을 다 더해 줬습니다.

코드

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

        //시작위치를 1로 초기화
        dp[1][1] = 1;
        //웅덩이들 -1로 초기화
        for (int[] puddle : puddles) {
            dp[puddle[1]][puddle[0]] = -1;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                // 웅덩이는 0 으로 바꾸고 넘어간다.
                if (dp[i][j] == -1) {
                    dp[i][j] = 0;
                } else {
                    if (i == 1) {
                        dp[i][j] += dp[i][j - 1];
                    } else {
                        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007;
                    }
                }

                //마지막 값 answer
                if (j == dp[i].length - 1) {
                    answer = dp[i][j];
                }
            }
        }
        return answer;
    }
}

느낀점

테스트케이스는 쉽게 통과해 빠르게 풀거라 생각했었습니다. 그런데 제출을 해보니 거의 대부분의 케이스를 통과 못 했습니다.
왜 그럴까 생각해보니 m, n 을 잘못 생각하고 있었다는것을 알게 되었습니다.
저는 웅덩이의 좌표는 n, m 이고 i, j 로 대입하면 될 것 이라 생각 했는데 글을 다시 읽어보니 m, n 이었습니다. 결국 j,i 로 대입해 풀었습니다.
문제의 조건을 재대로 파악 하지 못해 해맸던 문제 였습니다. 정말 문제의 조건을 잘 읽어야 겠다 생각이 들었습니다.