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

코딩테스트연습(동적계획법) - 등굣길

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

프로그래머스

문제 설명

집에서 출발하여 학교로 도착할 수 있는 모든 경로를 구하는 문제이다. 경로에 웅덩이가 있으면 돌아가야한다.

이동방향은 오른쪽과 아래만 가능하다.

경로를 1,000,000,007로 나눈 나머지를 출력한다.

---

문제 풀이

생각 과정

처음엔 단순 dfs로 생각하여 모든 경로를 탐색하며 학교좌표에 도착할 경우 count를 올려주는 방식으로 구현했다.

정확성테스트는 통과했지만 효율성 테스트를 실패했다.

지도 배열이 100*100이므로 대략 2^100의 연산이 필요하다.

다른 방법으로 구현해야했다.

 

문제조건에선 오른쪽과 아래방향으로만 이동이 가능하다고 했으므로 그것을 이용해보기로했다.

첫 칸은 방법이 한개 뿐이므로 1로 초기화 시켜준다.

그리고 0,1 좌표로 이동할 수 있는 것은 0,0 뿐이다 따라서 1을 입력해준다. (0,2 & 0,3 & 1,0 & 2,0 도 마찬가지)

다음으로 1,1 좌표로 이동할 수 있는 것은 0,1과 1,0이다. (오른쪽과 아래로 이동 가능하기 때문에)

따라서 0,1과 1,0에 저장되어 있는 값을 1,1에 더해준다.

이과정을 0,0부터 차례로 끝까지 진행한다.

이렇게 경로를 구하면 되는데 다만 웅덩이가 있는 경우에 미리 -1과 같은 값으로 입력해주어서 경로연산이 안되게 막아둬야한다.

구현

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

        for (int i = 0; i < puddles.length; i++) {
            int y = puddles[i][0];
            int x = puddles[i][1];
            arr[y][x] = -1;
        }
        arr[1][1] = 1;
        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if (arr[i][j] == -1) continue;
                if (i-1>0 && arr[i - 1][j] != -1) arr[i][j] += arr[i - 1][j] % 1000000007;
                if (j-1>0 && arr[i][j - 1] != -1) arr[i][j] += arr[i][j - 1] % 1000000007;
            }
        }
        return arr[m][n] % 1000000007;
    }
}

주의점

전체 배열의 크기를 지정할 때 m*n으로 구현을 했었는데 경계 처리가 까다로웠다. 이를 해결하기 위해 (m+1)*(n+1)로 구현을 하여 경계 범위가 벗어날 때 따로 if문으로 처리를 해주지 않아도 되게 변경했다.

(다 풀고 다시보니 문제에서 첫 좌표를 0,0이 아니라 1,1로 설정해서 힌트를 준게 아닌가 싶다...)