[Programmers] #42898 - 등굣길 [Java][C++][Python]

문제 링크

---

1. 아이디어

$(1, 1)$에서 $(m, n)$까지 오른쪽 또는 아래쪽으로만 이동하는 최단경로의 경우의 수를 구하는 전형적인 격자 DP 문제다. dp[i][j]를 $(i, j)$ 지점까지 도달하는 경로의 수로 정의하면, 오른쪽·아래쪽으로만 움직일 수 있으니 $(i, j)$에 도달하는 모든 경로는 반드시 바로 위 칸 $(i-1, j)$ 또는 바로 왼쪽 칸 $(i, j-1)$을 마지막으로 거쳐야 한다. 따라서 두 칸까지의 경로 수를 그대로 더한 dp[i][j] = dp[i-1][j] + dp[i][j-1]이 성립한다. 물에 잠긴 칸은 지나갈 수 없으므로 그 칸의 dp 값은 갱신하지 않고 기본값 0으로 남겨 이후 계산에서 자연스럽게 배제되도록 했다. 시작점 처리를 위해 dp[0][1] = 1로 미리 채워두면, $(1, 1)$ 계산 시 dp[0][1] + dp[1][0]이 1 + 0이 되어 시작점 자체가 경로 하나로 올바르게 잡힌다. 경로 수가 격자가 커질수록 기하급수적으로 커질 수 있으므로, 매 칸을 채울 때마다 1,000,000,007로 나눈 나머지를 저장해 오버플로를 방지했다.

---

2. 복잡도

접근	시간	공간
풀이	$O(NM)$	$O(NM)$

($N$, $M$ = 격자의 세로, 가로 길이)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {

    static int MOD = 1_000_000_007;

    public int solution(int m, int n, int[][] puddles) {
        boolean[][] chk = new boolean[1 + n][1 + m];
        for (int[] p : puddles) {
            chk[p[1]][p[0]] = true;
        }

        int[][] dp = new int[1 + n][1 + m];
        dp[0][1] = 1;

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

        return dp[n][m];
    }
}

#include <bits/stdc++.h>
using namespace std;

int MOD = 1'000'000'007;
bool chk[1 + 100][1 + 100];
int dp[1 + 100][1 + 100];

int solution(int m, int n, vector<vector<int>> puddles) {
    for (auto& p : puddles) {
        chk[p[1]][p[0]] = true;
    }

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

    return dp[n][m];
}

MOD = 1_000_000_007


def solution(m, n, puddles):
    chk = [[False] * (1 + m) for _ in range(1 + n)]
    for x, y in puddles:
        chk[y][x] = True

    dp = [[0] * (1 + m) for _ in range(1 + n)]
    dp[0][1] = 1

    for i in range(1, 1 + n):
        for j in range(1, 1 + m):
            if chk[i][j]:
                continue
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD

    return dp[n][m]

---