[코딩테스트] 8. 격자 DP

격자 DP는 2차원 배열에서 특정 위치에 도달하는 최적값을 구하는 패턴이다. 행과 열을 인덱스로 쓰므로 dp[i][j] 형태가 기본이다. 이동 방향 제약이 핵심이다.

기본 형태

N×M 격자에서 (0,0)에서 출발해 (N-1, M-1)에 도달하려 한다. 오른쪽과 아래쪽으로만 이동할 수 있을 때 경로 위 숫자의 최대 합은?

상태 정의 : dp[i][j] = (0,0)에서 (i,j)에 도달할 때의 최대 합

점화식 : (i,j)에 도달하는 방법은 위에서 오거나, 왼쪽에서 오거나.

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

dp[0][0] = grid[0][0];

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (i == 0 && j == 0) continue;
        int fromUp   = (i > 0) ? dp[i-1][j] : Integer.MIN_VALUE;
        int fromLeft = (j > 0) ? dp[i][j-1] : Integer.MIN_VALUE;
        dp[i][j] = Math.max(fromUp, fromLeft) + grid[i][j];
    }
}

위에서 오거나 왼쪽에서 오거나 — 두 경우 중 더 큰 값을 선택한다.

경계 처리

격자 DP에서 자주 실수하는 부분이 첫 행과 첫 열이다.

• 첫 행(i=0) : 위에서 오는 경로가 없다. 왼쪽에서만 올 수 있다
• 첫 열(j=0) : 왼쪽에서 오는 경로가 없다. 위에서만 올 수 있다

코드에서 (i > 0) 조건으로 처리하거나, 첫 행과 첫 열을 별도로 초기화하는 방법이 있다.

// 첫 행 초기화 (위에서 올 수 없으므로 왼쪽에서만)
for (int j = 1; j < m; j++) {
    dp[0][j] = dp[0][j-1] + grid[0][j];
}

// 첫 열 초기화 (왼쪽에서 올 수 없으므로 위에서만)
for (int i = 1; i < n; i++) {
    dp[i][0] = dp[i-1][0] + grid[i][0];
}

// 나머지
for (int i = 1; i < n; i++) {
    for (int j = 1; j < m; j++) {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    }
}

첫 행과 첫 열을 미리 처리해두면 본문 로직이 단순해진다.

이동 방향이 복잡해지면

오른쪽/아래만 이동하는 문제는 탐색 순서가 자연스럽게 위→아래, 왼→오른이다. 그런데 이동 방향이 추가되면 어떻게 될까.

좌우 이동이 허용되지만 위로는 갈 수 없고 재방문도 금지라면, 단순한 2D 점화식으로는 처리하기 어렵다. 이런 경우에는 행 단위로 분리해서 방향별 배열을 따로 만드는 기법을 쓴다.

→ 다음 : LIS

---