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

문제링크

문제

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

아래 그림은 m = 4, n = 3 인 경우입니다.

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

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

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

풀이

Brute force 접근을 한다면, 오른쪽과 아래쪽으로만 움직여서 중간에 물 웅덩이를 지나지 않는 경로들의 수를 모두 세면 된다.

dfs를 이용하여 도착한 곳이 웅덩이라면 넘어가는 식으로, 코드를 작성하면 될 것 같다. 하지만 brute force 접근 방법의 시간 복잡도는 2^(n+m)이다.

의사코드
void dfs(int x, int y) {  
    // 물 웅덩이를 만나면 더 이상 이 경로를 따라가지 않습니다.  
    if (grid[y][x] == 'puddle') return;  
  
    // 격자의 끝에 도달하면 카운터를 1 증가시킵니다.  
    if (x == m && y == n) {  
        count++;  
        return;  
    }  
  
    // 이동할 수 있는 경로를 탐색합니다. 여기서는 오른쪽과 아래로만 이동할 수 있다고 가정했습니다.  
    if (x+1 <= m) dfs(x+1, y);  
    if (y+1 <= n) dfs(x, y+1);  
}  
  
int main() {  
    // 시작 위치에서 시작  
    dfs(1, 1);  
    return count;  
}

따라서, 완전 탐색이 다른 접근을 고려해봐야한다. 격자 상에서 경로찾기 + 오른쪽과 아래쪽으로만 이동 이라는 조건에서, (i,j) 까지의 경로의 개수는 (i-1,j) 와 (i, j-1)까지 가는 경로의 개수를 서로 더한 값이 된다.

이를 통하여 큰 문제를 작은 문제로 분할하여 접근할 수 있게 되었다.

탑-다운(DP 메모이제이션) 방식

메모이제이션을 사용하는 탑-다운 접근법은 필요한 서브 문제만 해결하며 최종 문제를 해결

import java.util.*;  
  
class Solution {  
  
    // 모듈러 값 상수 선언  
    private static final int MOD = 1000000007;  
    // 동적 계획법 memoization을 위한 배열  
    private int[][] memo;  
    // 물웅덩이 위치 저장을 위한 배열  
    private int[][] puddles_map;  
  
    public int dp(int m, int n) {  
        // m이나 n이 1보다 작거나, 해당 위치가 웅덩이(-1)인 경우 0 반환  
        if (m < 1 || n < 1 || puddles_map[n][m] == -1) {  
            return 0;  
        }  
        // 처음 위치 (1,1)인 경우 경로 수는 1
        if (m == 1 && n == 1) {  
            return 1;  
        }  
        // 이미 계산된 값이 있다면 그 값을 반환  
        if (memo[n][m] != -1) {  
            return memo[n][m];  
        }  
  
        // 왼쪽과 위에서 오는 경로의 수를 합하고, 이 값에 MOD를 취한 값을 저장
        memo[n][m] = (dp(m - 1, n) + dp(m, n - 1)) % MOD;  
  
        // 계산된 값을 반환  
        return memo[n][m];  
    }  
  
    public int solution(int m, int n, int[][] puddles) {  
        // m by n 크기의 memo와 puddles_map 배열 초기화  
        memo = new int[n + 1][m + 1];  
        puddles_map = new int[n + 1][m + 1];  
  
        // 웅덩이 위치를 puddles_map에 표시  
        for (int[] puddle : puddles) {  
            puddles_map[puddle[1]][puddle[0]] = -1;  
        }  
  
        // memo 배열 초기화. 모두 -1로 채워진다.  
        for (int[] row : memo) {  
            Arrays.fill(row, -1);  
        }  
  
        // dp함수를 호출하여 m, n 위치까지 도달할 수 있는 경로의 수를 반환  
        return dp(m, n);  
    }  
}

바텀-업(DP 테이블) 방식:

표(tabulation)로 해결하는 바텀-업 접근법은 모든 서브 문제를 해결하며 최종 문제를 해결

class Solution {  
  
    private static final int MOD = 1000000007;  
  
    public int solution(int m, int n, int[][] puddles) {  
        // 각 지점까지 이동하는 최단 경로의 수를 저장할 dp 배열  
        int[][] dp = new int[n + 1][m + 1];  
        // 웅덩이가 있는 위치는 -1로 초기화  
        for (int[] puddle : puddles) {  
            dp[puddle[1]][puddle[0]] = -1;  
        }  
  
        for (int i = 1; i <= n; i++) {  
            for (int j = 1; j <= m; j++) {  
                // 시작점은 1로 초기화  
                if (i == 1 && j == 1) {  
                    dp[i][j] = 1;  
                }  
                // 웅덩이가 있는 위치라면, 해당 위치의 경로의 수는 0으로 초기화
                if (dp[i][j] == -1) {  
                    dp[i][j] = 0;  
                    continue;  
                }  
  
                // 위에서 온 경로의 수와 왼쪽에서 온 경로의 수를 더해준다.  
                if (i != 1) {  
                    dp[i][j] += dp[i - 1][j] % MOD;  
                }  
                if (j != 1) {  
                    dp[i][j] += dp[i][j - 1] % MOD;  
                }  
            }  
        }  
  
        return dp[n][m] % MOD;  
    }  
}

두가지 풀이 모두 시간 복잡도는 O(n*m)이 된다.

dp 풀이의 경우 탑-다운 <-> 바텀-업 변환이 자유로워야 한다.