programmers) 등굣길 | 두 번째 풀이

등굣길 문제를 두 번째로 풀면서 DP 접근 자체는 맞게 잡았다.

dp[y][x]에 시작점부터 (x, y)까지 이동하는 경우의 수를 저장하고, 위쪽과 왼쪽 값을 더하는 방식으로 구현했다.

다만 처음 제출한 코드에서는 구현 과정에서 몇 가지를 놓쳤다.

 

👉등굣길 - 첫풀이(문제포함)

1. 웅덩이 좌표 순서를 반대로 사용했다

문제에서 puddles는 [x, y] 형태로 주어진다.

하지만 DP 배열은 행, 열 순서로 사용했기 때문에 dp[y][x] 형태가 되어야 한다.

처음에는 아래처럼 작성했다.

dp[puddle[0]][puddle[1]] = -1;

하지만 올바른 코드는 아래와 같다.

dp[puddle[1]][puddle[0]] = -1;

배열을 new int[n + 1][m + 1]로 만들었기 때문에,

• 첫 번째 인덱스는 세로 길이인 y
• 두 번째 인덱스는 가로 길이인 x

로 사용해야 했다.

---

2. 시작점 값을 초기화하지 않았다

처음에는 dp[1][1]을 따로 설정하지 않았다.

하지만 출발점인 (1, 1)까지 도착하는 방법은 이미 한 가지이므로, 시작 전에 반드시 값을 넣어줘야 한다.

dp[1][1] = 1;

이 초기값이 없으면 배열은 모두 0에서 시작하고, 이후에도 위쪽과 왼쪽의 0만 더하게 된다.

---

3. 웅덩이 칸을 다시 계산하고 있었다

처음 코드에서는 웅덩이를 -1로 표시했지만, 반복문에서 해당 칸을 건너뛰지 않았다.

dp[j][k] = a + b;

이 코드가 실행되면 웅덩이로 표시한 -1 값도 일반 길처럼 다시 계산되어 덮어써질 수 있다.

그래서 현재 위치가 웅덩이인지 먼저 확인하고, 웅덩이라면 계산하지 않도록 수정했다.

if (dp[j][k] == -1) {
    continue;
}

---

4. a, b를 행마다 한 번만 초기화했다

처음 코드에서는 a, b를 안쪽 반복문 밖에서 선언했다.

for (int j = 1; j < n + 1; j++) {
    int a = 0;
    int b = 0;

    for (int k = 1; k < m + 1; k++) {
        // ...
    }
}

이렇게 하면 같은 행에서 다음 열을 계산할 때, 이전 열에서 사용한 a, b 값이 남을 수 있다.

특히 위쪽이나 왼쪽 칸이 웅덩이인 경우에는 값을 새로 대입하지 못하고, 이전 칸의 값이 그대로 사용될 가능성이 있다.

그래서 현재 칸을 계산할 때마다 0으로 초기화하도록 수정했다.

for (int j = 1; j <= n; j++) {
    for (int k = 1; k <= m; k++) {
        int a = 0;
        int b = 0;

        // 현재 칸 계산
    }
}

---

수정 후 핵심 코드

class Solution {
    private static final int MOD = 1_000_000_007;

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

        for (int[] puddle : puddles) {
            dp[puddle[1]][puddle[0]] = -1;
        }

        dp[1][1] = 1;

        for (int y = 1; y <= n; y++) {
            for (int x = 1; x <= m; x++) {

                if (y == 1 && x == 1) {
                    continue;
                }

                if (dp[y][x] == -1) {
                    continue;
                }

                int fromTop = 0;
                int fromLeft = 0;

                if (dp[y - 1][x] != -1) {
                    fromTop = dp[y - 1][x];
                }

                if (dp[y][x - 1] != -1) {
                    fromLeft = dp[y][x - 1];
                }

                dp[y][x] = (fromTop + fromLeft) % MOD;
            }
        }

        return dp[n][m];
    }
}

이번 두 번째 풀이에서는 DP 점화식보다 구현 세부 사항에서 실수했다.

특히 DP 문제에서는 아래 내용을 주의해서 확인해야겠다.

1. 시작점 초기값은 설정했는가?
2. 입력 좌표와 배열 인덱스 순서가 같은가?
3. 웅덩이처럼 계산하면 안 되는 칸을 건너뛰고 있는가?
4. 반복문 안에서 사용하는 임시 변수 값이 이전 칸에 영향을 받지 않는가?