Algorithms/Dynamic Programming

2.15.2 Grid DP

개념

이동 방향이 오른쪽과 아래쪽으로 제한된 격자에서는 현재 칸의 답을 위쪽과 왼쪽 칸의 답으로 구할 수 있습니다.

각 칸까지 가는 경로 수

Di,jD_{i,j}를 시작점에서 (i,j)(i,j)까지 오는 경로 수로 정의합니다. 이동 가능한 칸이면 위에서 내려오는 경로와 왼쪽에서 오는 경로를 더합니다.

Di,j=Di−1,j+Di,j−1.D_{i,j}=D_{i-1,j}+D_{i,j-1}.

벽의 값은 00입니다. 시작점은 11로 설정하고, 격자 밖에서 오는 경우는 00으로 처리합니다. 행과 열을 작은 번호부터 확인하면 필요한 두 상태가 먼저 계산됩니다.

도착 직전의 이동은 위에서 내려오거나 왼쪽에서 들어오는 두 경우뿐입니다. 두 경우의 마지막 간선이 다르므로 경로가 중복되지 않아 두 경로 수를 더할 수 있습니다.

벽이 있는 격자에서 값 채우기

다음 4×54\times5 격자에서 (1,1)(1,1)부터 (4,5)(4,5)까지 이동하겠습니다. (2,3)(2,3)과 (3,2)(3,2)는 벽입니다. 그림의 X는 벽, 빈칸은 아직 계산하지 않은 칸이며, 숫자는 해당 칸까지 오는 경로 수입니다.

1 2 3 4 5 1 1 2 3 4
▲ [그림 1] 시작점은 1, 벽은 경로 수 0으로 처리

첫 행은 오른쪽으로만, 첫 열은 아래쪽으로만 도달하므로 각각 11가지입니다. (2,2)(2,2)는 위쪽 (1,2)(1,2)와 왼쪽 (2,1)(2,1)에서 각각 11가지씩 도달하여 1+1=21+1=2가 됩니다.

(3,3)(3,3)은 이동 가능한 칸이지만 위쪽 (2,3)(2,3)과 왼쪽 (3,2)(3,2)가 모두 벽입니다. 따라서 경로 수는 0+0=00+0=0입니다. 이동 가능한 칸도 시작점에서 도달할 수 없으면 00으로 남습니다.

행마다 왼쪽부터 계산하면 마지막 칸을 채우기 직전의 상태는 다음과 같습니다. 진한 두 칸은 도착점으로 들어오는 위쪽 칸과 왼쪽 칸입니다.

1 2 3 4 5 1 1 1 1 1 1 2 1 2 1 2 3 1 0 1 3 4 1 1 1 2
▲ [그림 2] 도착점 위쪽은 3가지, 왼쪽은 2가지

도착점 (4,5)(4,5)에는 (3,5)(3,5)에서 아래로 내려오는 33가지와 (4,4)(4,4)에서 오른쪽으로 이동하는 22가지가 있습니다. 마지막 이동 방향이 달라 서로 겹치지 않으므로 D4,5=3+2=5D_{4,5}=3+2=5입니다.

1 2 3 4 5 1 1 1 1 1 1 2 1 2 1 2 3 1 0 1 3 4 1 1 1 2 5
▲ [그림 3] 두 경로 수를 더해 도착점의 값 5 계산

오른쪽과 아래쪽으로만 이동하므로 먼저 계산한 위·왼쪽 상태가 현재 칸에 다시 의존하지 않습니다. 자유롭게 네 방향으로 이동해 이전 칸으로 돌아올 수 있는 문제라면 같은 계산 순서를 적용할 수 있는지 별도로 확인해야 합니다. 최소 이동 횟수를 구하는 격자 문제에서는 BFS를 사용할 수 있습니다.

복잡도

행 수를 RR, 열 수를 CC라고 합니다. 경로에 점수가 있다면 최소·최대 점수를 기록하는 상태로 확장할 수 있습니다.

연산시간복잡도공간복잡도
격자 DPO(RC)O(RC)격자·DP 표 O(RC)O(RC)

예제

문제

왼쪽 위에서 오른쪽 아래까지 오른쪽 또는 아래쪽으로만 이동하는 경로의 수를 구하여라.

입력

첫째 줄에 행 수 RR과 열 수 CC가 공백을 사이에 두고 주어진다. 1≤R,C≤101\le R,C\le10이다.

다음 RR개 줄에 길이가 CC인 문자열이 주어진다. 각 문자열은 0과 1이 공백 없이 나열된 형태이다. 1은 이동 가능한 칸, 0은 벽이다. 시작 칸과 도착 칸은 1이다.

출력

가능한 경로 수를 출력한다.

예제 입력

4 5
11111
11011
10111
11111

예제 출력

5

예제 코드

C++20

#include <iostream>
#include <string>

using namespace std;

int dp[11][11];
string g[10];

int main() {
    int n, m, i, j;

    cin >> n >> m;
    for (i = 0; i < n; ++i) {
        cin >> g[i];
    }
    // 시작 칸에 도착한 경우 한 가지로 초기화
    dp[1][1] = 1;
    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= m; ++j) {
            if (i == 1 && j == 1) continue;
            // 현재 칸으로 오는 위쪽 경로와 왼쪽 경로의 수를 합침
            if (g[i - 1][j - 1] == '1') dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    cout << dp[n][m] << '\n';
}