[프로그래머스 / Level3] 등굣길 (Java)

문제 보기

---

사용한 것

• 2차원 배열의 (1, 1)에서 (m, n)까지 가는 경로의 경우의 수를 구하기 위한 bottom up

---

풀이 방법

• bottom up으로 경로의 수를 저장할 dp를 할당한다.
• 물에 잠긴 지역은 dp에 -1을 넣어준다.
• 1열과 1행으로 가는 방법은 항상 하나 밖에 없으므로 1을 넣는다.
  • 이 때 물에 잠긴 지역을 만나면 그 뒤로는 넣어주지 않는다. (갈 수 없으므로)
• bottom up을 시작하여 위에서 오는 경우의 수와 왼쪽에서 오는 경우의 수를 더해서 해당 (i, j)에 넣어준다.
  • 해당 좌표가 물 웅덩이인 경우는 패스한다.
  • 위, 왼쪽의 좌표가 물 웅덩이면 -1 대신 0을 더해준다.
  • 더해서 넣어줄 때 1,000,000,007의 나머지를 넣어준다 (문제 조건)
• (1, 1)에서 (m, n)까지 가는 경로의 경우의 수인 dp[m][n]을 반환한다.

---

코드

class Solution {

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

        for (int i = 0; i < puddles.length; i++) {
            dp[puddles[i][0]][puddles[i][1]] = -1;
        }

        for (int i = 2; i <= m; i++) {
            if (dp[i][1] == -1) {
                break;
            }

            dp[i][1] = 1;
        }

        for (int i = 2; i <= n; i++) {
            if (dp[1][i] == -1) {
                break;
            }

            dp[1][i] = 1;
        }

        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                if (dp[i][j] == -1) {
                    continue;
                }

                int up = dp[i - 1][j] == -1 ? 0 : dp[i - 1][j];
                int left = dp[i][j - 1] == -1 ? 0 : dp[i][j - 1];
                dp[i][j] = (up + left) % 1_000_000_007;
            }
        }

        return dp[m][n];
    }
}

---