[알고리즘 - DP] 프로그래머스 - 등굣길

문제

문제 링크

풀이

문제 이해

아래와 같은 m x n 크기의 격자가 있을 때,

가장 왼쪽 위 (1, 1) 에서 가장 우측 아래쪽 (m, n) 으로 가는 방법의 개수를 구하는 문제이다. (1,000,000,007로 나눈 나머지 반환) 단, 이때 위 그림에서처럼 웅덩이가 있는 곳은 지나가지 못한다.

입력으로는 격자의 크기 m, n과 웅덩이의 좌표가 [[2, 2]]와 같은 형태로 puddles 이름으로 제공된다.

풀이 방법

문제에서 우측 및 아래로 움직이는 경로만 가능하다고 했으므로 (1, 1)에서 시작하여 (m, n)까지 우측 및 아래로 한 칸씩 이동하며 경로의 개수를 계산한다. 이때, 예를 들어 (3, 3)까지의 경로 경우의 수는 아래와 같이 (2, 3) 까지의 경로 경우의 수와 (3, 2) 까지의 경로 경우의 수를 더한 값과 같다.

이런식으로 계속 반복하다보면 (m, n) 위치의 경우의 수도 아래와 같이 구할 수 있다.

따라서 점화식을 세워보면, answer[m, n] = answer[m - 1][n] + answer[m][n-1] 이라 할 수 있다.

이제 위 점화식을 사용해 코드를 작성하면 되는데 아래 두 가지를 고려해야 한다.

1. 웅덩이에 접근하는 경로(puddles)는 사용하지 않을 것
2. 한 번 구한 경로는 다시 계산하지 않도록 메모이제이션을 적용할 것

위 점들을 고려해 재귀로 작성한 코드는 아래와 같다.

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

        // 물에 잠긴 지역 별도 배열로 생성
        int[][] processedPuddles = new int[m + 1][n + 1];
        for (int i = 0 ; i < puddles.length ; i++) {
            processedPuddles[puddles[i][0]][puddles[i][1]] = -1;
        }

        // 재귀 호출
        return search(m, n, m, n, answer, processedPuddles);
    }

    public int search(int m, int n,
                       int x, int y,
                       int[][] answer, int[][] processedPuddles) {
        // 초기 케이스
        if (x == 1 && y == 1) {
            return 1;
        }
        // 범위를 벗어나면 제외
        if (x > m || x < 1 || y > n || y < 1) {
            return 0;
        }
        // 물에 잠긴 지역은 제외
        if (processedPuddles[x][y] == -1) 
            return 0;

        // 메모이제이션
        if (answer[x][y] != 0) {
            return answer[x][y];
        }

        // 나머지 정상 케이스
        return answer[x][y] = (search(m, n, x - 1, y, answer, processedPuddles) 
                               + search(m, n, x, y - 1, answer, processedPuddles)) 
                                % 1_000_000_007;
    }
}

근데 뭔가 짜고 보니 재귀보다 반복이 더 보기 좋을 것 같아서 다시 작성했다. ㅎㅎ

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

        // 물에 잠긴 지역 처리
        for (int i = 0 ; i < puddles.length ; i++) {
            answer[puddles[i][0]][puddles[i][1]] = -1;
        }

        // 초기 좌표 값 설정
        answer[1][1] = 1;

        // 순회하며 경우의 수 계산
        for (int x = 1 ; x <= m ; x++) {
            for (int y = 1 ; y <= n ; y++) {
                // 물에 잠긴 지역 제외
                if (answer[x][y] == -1) {
                    answer[x][y] = 0;
                    continue;
                }

                // 나머지 정상 경로 계산
                if (x != 1) {
                    answer[x][y] += answer[x - 1][y] % 1_000_000_007;
                }
                if (y != 1) {
                    answer[x][y] += answer[x][y - 1] % 1_000_000_007;
                }
            }
        }
        return answer[m][n] % 1_000_000_007;
    }
}

코드에서 주의해야 할 부분들은 아래와 같다.

1. 계산을 모두 마치고 반환할 때만 1,000,000,007로 나눈 나머지를 반환하는 것과 매번 나누고 더해주는 것의 값 차이는 없으나 후자의 방법을 사용해야 효율성 테스트에서 탈락하지 않는다.
2. 물에 잠긴 지역을 처리할 때 순회 방식으로 하게 되면 물에 잠긴 지역을 단 한 번만 방문하기 때문에 굳이 별도의 배열을 사용하지 않고 answer 배열에 -1 등으로 저장해두고 해당 좌표를 지나갈 때 0으로 값을 바꿔주면서 continue 처리해주면 해당 좌표를 경로로 사용하지 않도록 처리가 가능하다.
3. 초기 좌표 값에 위치하는 경우의 수는 한 가지이므로 answer[1][1]은 1로 초기화해준다.
4. 순회로 풀이하는 경우 x가 1가 아닐 때 좌측 좌표의 경우의 수를 현재 좌표에 더해주고, y가 1이 아닐 때 위쪽 좌표의 경우의 수를 현재 좌표에 더해준다.