이 튜토리얼에서는 C++ 프로그램을 사용하여 행렬에서 위쪽 행부터 아래쪽 행까지 이동하는 경로 중 합이 최대가 되는 경로를 찾는 방법을 다룹니다.
문제 정의
N×N 크기의 행렬이 주어졌을 때, 첫 번째 행에서 시작하여 마지막 행에 도달하는 경로 중 원소 값의 합이 가장 큰 경로를 구해야 합니다. 이때 이동 규칙은 현재 위치에서 바로 아래 대각선 방향(왼쪽 아래 또는 오른쪽 아래)의 칸으로만 이동할 수 있습니다.
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 아래에서부터 거꾸로 올라가며 각 칸에서 도달 가능한 최대 합을 저장하고, 마지막에 첫 번째 행의 값들 중 최댓값을 선택하는 방식입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
// 최대 합 경로를 찾는 함수
int maxSum(int mat[SIZE][SIZE], int n) {
if (n == 1)
return mat[0][0];
int dp[n][n];
int maxSum = INT_MIN, max;
// 마지막 행 초기화
for (int j = 0; j < n; j++)
dp[n - 1][j] = mat[n - 1][j];
// 아래에서 위로 올라가며 DP 테이블 채우기
for (int i = n - 2; i >= 0; i--) {
for (int j = 0; j < n; j++) {
max = INT_MIN;
if (((j - 1) >= 0) && (max < dp[i + 1][j - 1]))
max = dp[i + 1][j - 1];
if (((j + 1) < n) && (max < dp[i + 1][j + 1]))
max = dp[i + 1][j + 1];
dp[i][j] = mat[i][j] + max;
}
}
// 첫 번째 행에서 최댓값 찾기
for (int j = 0; j < n; j++)
if (maxSum < dp[0][j])
maxSum = dp[0][j];
return maxSum;
}
int main() {
int mat[SIZE][SIZE] = {
{ 5, 6, 1, 7 },
{ -2, 10, 8, -1 },
{ 3, -7, -9, 11 },
{ 12, -4, 2, 6 }
};
int n = 4;
cout << "Maximum Sum = " << maxSum(mat, n);
return 0;
}실행 결과
Maximum Sum = 28
동작 원리 설명
위 코드의 핵심 로직은 다음과 같습니다.
1. DP 테이블 초기화: 먼저 행렬의 마지막 행 값을 그대로 DP 테이블의 마지막 행에 복사합니다. 마지막 행은 더 이상 내려갈 곳이 없기 때문입니다.
2. 아래에서 위로 계산: 마지막에서 두 번째 행부터 시작해 위쪽으로 이동하면서, 각 칸 dp[i][j]에는 해당 칸의 값 mat[i][j]에 바로 아래 대각선 두 칸(dp[i+1][j-1], dp[i+1][j+1]) 중 더 큰 값을 더한 결과를 저장합니다. 행렬의 가장자리에 있는 경우 배열 범위를 벗어나지 않도록 조건 검사를 수행합니다.
3. 결과 도출: 모든 계산이 끝나면 첫 번째 행의 DP 값들 중 최댓값이 곧 전체 경로의 최대 합이 됩니다.
예제 행렬의 경우, 경로 7 → 10 → 11 → ... 와 같이 대각선으로 이동하며 합산했을 때 최대 합 28을 얻을 수 있습니다.
시간 및 공간 복잡도
- 시간 복잡도: O(N²) — 행렬의 모든 칸을 한 번씩 방문합니다.
- 공간 복잡도: O(N²) — DP 테이블을 위해 추가 배열이 필요합니다. (두 개의 1차원 배열만 사용하면 O(N)까지 최적화 가능)
이처럼 동적 계획법을 활용하면 모든 경로를 일일이 탐색하는 완전 탐색(O(2ᴺ)) 방식보다 훨씬 효율적으로 최대 합 경로 문제를 해결할 수 있습니다.