이번 문제에서는 크기가 M×N인 2차원 행렬이 주어졌을 때, 행렬 내 최대 경로 합(Maximum Path Sum)을 찾는 프로그램을 작성해야 합니다.
여기서 말하는 최대 경로 합은 첫 번째 행의 원소에서 출발하여 마지막 행의 원소에 도달할 때까지 지나가는 모든 원소 값의 합을 의미합니다. 이때 경로 탐색에 허용되는 이동은 다음과 같습니다.
- 아래 방향 이동: 바로 아래 행의 같은 열로 이동
- 대각선 이동: 아래 행의 왼쪽 또는 오른쪽 대각선 칸으로 이동
즉, 시작점은 첫 번째 행의 어느 원소든 될 수 있고, 끝점 역시 마지막 행의 어느 원소든 될 수 있습니다.
문제 예시
구체적인 예시를 통해 문제를 살펴보겠습니다.
입력 −
matrix [][] =
3 5 9
1 7 2
4 8 6
출력 − 24
설명 − 최대 경로는 9 → 7 → 8이며, 각 원소의 합은 3 + ... 즉 9 + 7 + 8 = 24가 됩니다.
접근 방법: 동적 계획법(DP)
모든 가능한 경로를 일일이 탐색하는 것은 비효율적이므로, 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 두 번째 행부터 마지막 행까지 순서대로 순회합니다.
- 각 칸 (i, j)에는 바로 위 행에서 해당 칸으로 올 수 있는 위치들(같은 열, 왼쪽 대각선, 오른쪽 대각선) 중 최댓값을 현재 값에 더해 누적합니다.
- 행렬의 양 끝 열(첫 번째 열, 마지막 열)은 이동 가능한 위치가 2개뿐이므로 경계 조건을 따로 처리해야 합니다.
- 순회가 끝나면 마지막 행의 값들은 각 열에서 시작한 경로 중 그 지점에 도달하는 최대 합을 담고 있으므로, 마지막 행의 최댓값이 곧 정답이 됩니다.
이 방식의 시간 복잡도는 O(M×N), 공간 복잡도는 입력 행렬을 직접 갱신하는 경우 O(1)의 추가 메모리로 해결할 수 있습니다.
C++ 구현 예제
다음은 행렬의 최대 경로 합을 구하는 C++ 프로그램입니다.
#include <iostream>
#define N 3
#define M 3
using namespace std;
int maxPathSum(int mat[][M]){
// 두 번째 행부터 각 칸에 도달 가능한 최대 경로 합을 누적
for (int i = 1; i < N; i++) {
for (int j = 0; j < M; j++) {
if (j > 0 && j < M - 1)
mat[i][j] += max(mat[i - 1][j], max(mat[i - 1][j - 1], mat[i - 1][j + 1]));
else if (j > 0)
mat[i][j] += max(mat[i - 1][j], mat[i - 1][j - 1]);
else if (j < M - 1)
mat[i][j] += max(mat[i - 1][j], mat[i - 1][j + 1]);
}
}
// 마지막 행의 최댓값이 전체 최대 경로 합
int maxSum = mat[N-1][0];
for (int j = 1; j < M; j++)
maxSum = max(mat[N-1][j], maxSum);
return maxSum;
}
int main(){
int matrix[N][M] = {
{3, 5, 9 },
{1, 7, 2},
{4, 8, 6}};
cout<<"The maximum path sum of matrix is : "<<maxPathSum(matrix);
return 0;
}
실행 결과
The maximum path sum of matrix is : 24
정리
행렬 최대 경로 합 문제는 단순히 모든 경로를 탐색하는 대신, 각 칸에 도달할 수 있는 최대 값을 위쪽 행부터 차례로 누적해 나가는 동적 계획법으로 해결할 수 있습니다. 이 접근법은 O(M×N)의 시간 안에 최적의 해를 보장하며, 격자 형태의 경로 탐색 문제(예: 삼각형 경로 합, 최소 경로 합 등)에도 동일한 패턴으로 응용할 수 있습니다.