문제 개요
문자로 이루어진 정사각형 보드가 있다고 가정해 봅시다. 보드의 오른쪽 아래 끝 칸에는 시작점을 나타내는 'S'가, 왼쪽 위 끝 칸에는 도착점을 나타내는 'E'가 표시되어 있습니다. 나머지 칸은 1부터 9 사이의 숫자 문자이거나 장애물 'X'입니다. 한 번의 이동으로는 위쪽, 왼쪽, 왼쪽 위 대각선 세 방향 중 하나로만 움직일 수 있으며, 이동하려는 칸에 장애물이 있다면 그 방향으로는 진행할 수 없습니다.
우리가 구해야 하는 것은 다음 두 값을 담은 리스트입니다.
첫 번째 값: 이동 과정에서 수집할 수 있는 숫자들의 최대 합
두 번째 값: 그 최대 합을 달성할 수 있는 서로 다른 경로의 개수
답은 반드시 10^9 + 7로 나눈 나머지를 반환해야 하며, 도달 가능한 경로가 하나도 없다면 [0, 0]을 반환합니다.
예를 들어 입력이 board = ["E12", "1X1", "21S"]와 같다면 출력은 [1, 2]가 됩니다.
해결 전략: 동적 계획법(DP)
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심은 각 칸마다 두 가지 정보를 동시에 관리하는 것입니다. 즉, 해당 칸에서 도착점까지 이동했을 때 얻을 수 있는 최대 점수(dp[i][j][0])와, 그 점수를 얻을 수 있는 경로의 수(dp[i][j][1])를 함께 저장합니다.
구체적인 풀이 순서는 다음과 같습니다.
n := 행의 개수, m := 열의 개수로 설정합니다.
n × m × 2 크기의 3차원 배열 dp를 선언합니다. 인덱스 0에는 최대 점수를, 인덱스 1에는 경로의 수를 저장합니다.
시작점을 초기화합니다: dp[n-1][m-1][0] = 0, dp[n-1][m-1][1] = 1
마지막 행을 오른쪽에서 왼쪽으로 순회하며 처리합니다(장애물 'X'를 만나면 중단).
dp[n-1][i][0] = 현재 칸의 숫자 값 + dp[n-1][i+1][0]
dp[n-1][i][1] += dp[n-1][i+1][1]
마지막 열도 같은 방식으로 아래에서 위로 순회하며 처리합니다.
나머지 내부 칸들을 오른쪽 아래에서 왼쪽 위 방향으로 순회하며 다음을 수행합니다.
현재 칸이 'X'(장애물)이면 건너뜁니다.
현재 칸의 기본 점수를 설정합니다. 'E'라면 0, 숫자라면 해당 숫자 값입니다.
오른쪽(dp[i][j+1]), 아래(dp[i+1][j]), 오른쪽 아래 대각선(dp[i+1][j+1]) 세 방향의 점수 중 최댓값(maxVal)을 구합니다.
maxVal이 0이면서 세 인접 칸 어디에도 'S'가 없다면, 도달 가능한 경로가 없다는 의미이므로 현재 칸의 점수를 0으로 설정하고 다음 칸으로 넘어갑니다.
그렇지 않다면 현재 칸의 점수에 maxVal을 더하고, 점수가 maxVal과 일치하는 모든 방향의 경로 수를 현재 칸의 경로 수에 누적합니다.
점수와 경로 수에 각각 모듈로 연산(10^9 + 7)을 적용합니다.
모든 계산이 끝나면 dp[0][0]을 반환합니다.
이 알고리즘의 시간 복잡도는 O(n×m), 공간 복잡도 역시 O(n×m)로, 보드의 모든 칸을 한 번씩만 확인하면 되므로 매우 효율적입니다.
C++ 구현 예제
아래 코드를 통해 실제 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
} cout << "]"<<endl;
}
typedef long long int lli;
const lli m = 1e9 + 7;
lli add(lli a, lli b){
return ((a % m) + (b % m) % m);
}
class Solution {
public:
vector<int> pathsWithMaxScore(vector<string>& b) {
int n = b.size();
int m = b[0].size();
vector < vector < vector <int> > > dp(n, vector < vector
<int> >(m, vector <int> (2)));
dp[n - 1][m - 1][0] = 0;
dp[n - 1][m - 1][1] = 1;
for(int i = m - 2; i >= 0; i--){
if(b[n - 1][i] == 'X')break;
dp[n - 1][i][0] = b[n - 1][i] - '0' + dp[n - 1][i + 1]
[0];
dp[n - 1][i][1] += dp[n - 1][i + 1][1];
}
for(int i = n - 2; i >= 0; i--){
if(b[i][m - 1] == 'X')break;
dp[i][m - 1][0] = b[i][m - 1] - '0' + dp[i + 1][m - 1]
[0];
dp[i][m - 1][1] += dp[i + 1][m - 1][1];
}
for(int i = n - 2; i >= 0; i--){
for(int j = m - 2; j >= 0; j--){
if(b[i][j] == 'X')continue;
dp[i][j][0] = b[i][j] == 'E' ? 0 :b[i][j] - '0';
int maxVal = max({dp[i][j + 1][0], dp[i + 1][j][0],
dp[i + 1][j + 1][0]});
if(maxVal == 0 && (b[i+1][j] != 'S' && b[i][j + 1] !
= 'S' && b[i+1][j + 1] != 'S')){
dp[i][j][0] = 0;
continue;
}
dp[i][j][0] += maxVal;
if(dp[i + 1][j][0] == maxVal){
dp[i][j][1] += dp[i + 1][j][1];
}
if(dp[i + 1][j + 1][0] == maxVal){
dp[i][j][1] += dp[i + 1][j + 1][1];
}
if(dp[i][j + 1][0] == maxVal){
dp[i][j][1] += dp[i][j + 1][1];
}
dp[i][j][1] %= m;
dp[i][j][0] %= m;
}
}
return dp[0][0];
}
};
main(){
Solution ob;
vector<string> v = {"E12","1X1","21S"};
print_vector(ob.pathsWithMaxScore(v));
}
입력
{"E12","1X1","21S"}
출력
[1, 2]
마무리
이 문제의 핵심은 단순히 최댓값만 추적하는 것이 아니라, 최댓값을 만들어내는 경로의 개수를 함께 누적한다는 점입니다. 세 방향(위, 왼쪽, 대각선)의 DP 값을 비교하여 최댓값과 일치하는 모든 방향의 경로 수를 더해주면, 자연스럽게 최대 점수를 얻는 모든 경로를 셀 수 있습니다. 이러한 패턴은 격자(grid) 기반 경로 탐색 문제에서 자주 활용되므로 잘 익혀두면 다양한 응용 문제에 도움이 됩니다.