← Back

격자 위 최적 경로를 찾는 DP

격자 위를 정해진 방향으로 한 칸씩 움직이며 지나온 칸의 합을 최대(또는 최소)로 만드는 문제를 푸는 DP 유형이다. 여기서는 이동 경로에 순환이 없어, 이전 칸의 답부터 차례로 계산할 수 있는 경우를 다룬다.

되돌아갈 수 있다면: 계산 순서에 순환이 생길 수 있다. 이동 횟수 등을 상태에 추가하거나, 문제에 맞는 그래프 탐색이나 최단 경로 알고리즘을 고려해야 한다.


핵심 아이디어

같은 칸에 도착했다면, 어떤 길로 왔든 그다음에 갈 수 있는 길은 같다. 앞으로의 결과를 가르는 건 지금 위치와 지금까지의 합뿐이다.

그래서 같은 칸에 도착한 경로들 중 합이 가장 좋은 하나만 남기면 된다. 경로를 전부 따지면 경우의 수가 빠르게 늘지만, 각 칸에 들어오는 방향이 일정한 개수라면 이렇게 해서 칸 수만큼만 계산할 수 있다.

풀이 틀

단계이 유형에서는
상태 정의dp[i][j] = (i, j)에 도착했을 때의 최적값
점화식들어올 수 있는 이전 칸들의 dp 중 최적값 + 현재 칸의 값
초기 조건시작 칸, 그리고 들어오는 길이 하나뿐인 가장자리 칸
답도착 칸의 dp (도착 지점이 여러 곳이면 그중 최적값)

‘이전 칸’은 이동 규칙을 거꾸로 보면 찾을 수 있다. 오른쪽과 아래로 움직인다면 (i, j)에는 위 (i-1, j)나 왼쪽 (i, j-1)에서만 들어온다.

채우는 순서

점화식은 이전 칸이 먼저 채워져 있어야 쓸 수 있다. 움직임이 위에서 아래로, 왼쪽에서 오른쪽으로 향한다면 평소 이중 for문 순서대로 채우기만 해도 이 조건이 지켜진다.

예제

가장 기본적인 형태로 풀어보자. n행 m열 격자의 칸마다 숫자가 적혀 있고, 왼쪽 위 (0, 0)에서 출발해 오른쪽 또는 아래로 한 칸씩 움직여 오른쪽 아래 (n-1, m-1)까지 간다. 이때 지나온 칸의 숫자 합의 최댓값을 구한다.

2 1 3
4 1 2
1 5 1

이 격자라면 2 → 4 → 1 → 5 → 1로 가는 길의 합 13이 답이다. 위의 풀이 틀대로 옮기면 코드는 다음과 같다. n과 m은 1 이상이고, 경로의 합은 int 범위 안에 있다고 가정한다.

// a[i][j]: (i, j) 칸에 적힌 값 (입력, n행 m열)
// dp[i][j]: (i, j)까지 왔을 때의 최대 합 (우리가 채울 표)
int[][] dp = new int[n][m];

// 초기 조건
dp[0][0] = a[0][0];
for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + a[i][0]; // 첫 열: 위에서만 들어옴
for (int j = 1; j < m; j++) dp[0][j] = dp[0][j - 1] + a[0][j]; // 첫 행: 왼쪽에서만 들어옴

// 점화식
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]) + a[i][j]; // 위 칸과 왼쪽 칸 중 큰 쪽을 고름

// 답
int ans = dp[n - 1][m - 1];

각 칸을 한 번씩 계산하므로 시간복잡도는 O(nm) 이고, dp 배열의 공간복잡도도 O(nm) 이다. 최솟값을 구한다면 같은 조건에서 Math.max()를 Math.min()으로 바꾸면 된다.


이동 규칙이 달라지면 점화식의 이전 칸과 가장자리 초기 조건, 채우는 순서를 다시 확인하면 된다. 예를 들어 아래와 오른쪽 아래 대각선으로 움직인다면 이전 칸은 (i-1, j)와 (i-1, j-1)이다. 이때는 도달할 수 없는 칸도 생길 수 있으므로, 그런 상태를 최적값 후보에 넣지 않도록 처리해야 한다.

← Back