📝 등굣길 (Level 3)

동적 계획법 (Dynamic Programming)
등굣길

🔹Python

• 다른 사람의 풀이

def solution(m, n, puddles):
    dp = [[0] * (m + 1) for _ in range(n + 1)] # dp 테이블 초기화
    dp[1][1] = 1
    
    for i, j in puddles: # 웅덩이가 있는 곳은 -1로 표시
        dp[j][i] = -1 # (x, y) -> x는 열(column), y는 행(row)
        
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if dp[i][j] == -1: # 웅덩이이면
                dp[i][j] = 0 # 이후 값에 영향을 주지 않게 하기 위해 0으로 바꾸고
                continue # 건너뜀
                
            # 위에서 오는 경우와 왼쪽에서 오는 경우를 더해줌
            dp[i][j] += (dp[i - 1][j] + dp[i][j - 1]) % 1000000007
            
    return(dp[n][m])

1. DP 테이블 초기화:
   dp라는 이름의 2차원 리스트를 만듭니다. 이 리스트는 격자에 해당하는 크기(n+1 x m+1)로 초기화되며, 모든 값을 0으로 설정합니다. dp[1][1]을 1로 설정하여, 시작 위치에서의 경로 수를 1로 만듭니다.

2. 웅덩이 위치 표시:
   puddles 리스트에 있는 좌표를 순회하면서, 웅덩이 위치를 dp 테이블에서 -1로 표시합니다. 이때 웅덩이 위치를 dp[i][j]가 아니라 dp[j][i]로 표시하는 이유는 puddles 리스트의 좌표가 (x, y)로 주어지는데, x는 열(column)에, y는 행(row)에 해당하기 때문입니다.

3. 경로 계산:
   dp 테이블을 순회하면서 각 위치에 도달할 수 있는 경로의 개수를 계산합니다. 특정 위치가 웅덩이(-1)이면, 그 위치의 값을 0으로 바꾸고, 이후 계산에 영향을 미치지 않도록 건너뜁니다.
   (0으로 바꿔서 웅덩이는 계산이 안되도록)
   그렇지 않으면, 현재 위치 dp[i][j]에서 위쪽에서 오는 경로(dp[i-1][j])와 왼쪽에서 오는 경로(dp[i][j-1])를 더해줍니다. 이때 큰 수를 처리하기 위해 1000000007로 나눈 나머지를 저장합니다.

4. 결과 반환:
   마지막 위치인 dp[n][m]에 도달하는 경로의 개수를 반환합니다.

• 질문에 대한 답변:
  puddles 리스트는 (x, y) 형태로 주어지며, 여기서 x는 열(column)에, y는 행(row)에 해당합니다. 하지만 일반적으로 dp 테이블은 dp[i][j]에서 i가 행(row)을, j가 열(column)을 의미합니다. 그래서 puddles에서 (i, j)를 가져올 때, 이를 dp 테이블의 dp[j][i] 위치에 대응시키기 위해 dp[j][i] = -1로 설정하는 것입니다.
  예를 들어, puddles에 (2, 3)이 있으면, 이 좌표는 2열(column), 3행(row)에 위치한 웅덩이를 나타냅니다. 이를 dp 테이블에 반영할 때, dp[3][2] = -1로 설정하여 3행 2열 위치를 웅덩이로 표시하는 것입니다.

---

🔸Java

public class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] dp = new int[n + 1][m + 1]; // dp 테이블 초기화
        dp[1][1] = 1;
        
        // 웅덩이 있는 곳을 -1로 표시
        for (int[] puddle : puddles) {
            dp[puddle[1]][puddle[0]] = -1; // (x, y) -> x는 열(column), y는 행(row)
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (dp[i][j] == -1) { // 웅덩이이면
                    dp[i][j] = 0; // 이후 값에 영향을 주지 않게 하기 위해 0으로 바꾸고
                    continue; // 건너뜀
                }
                
                // 위에서 오는 경우와 왼쪽에서 오는 경우를 더해줌
                dp[i][j] += (dp[i - 1][j] + dp[i][j - 1]) % 1000000007 ;
            }
        }
        
        return dp[n][m]; // 결과 반환
    }
}

Java에서 2차원 배열을 int[][] dp = new int[n + 1][m + 1];로 초기화할 때, 이 배열은 고정된 크기를 가지지만, 각 요소의 값은 언제든지 변경할 수 있습니다. 즉, 배열의 크기는 고정되지만 배열 내부의 값들은 변경 가능합니다.

// 웅덩이 있는 곳을 -1로 표시
        for (int[] puddle : puddles) {
            dp[puddle[1]][puddle[0]] = -1; // (x, y) -> x는 열(column), y는 행(row)
        }

2차원 배열의 값을 어떻게 바꾸는지 몰랐었다...