C++로 0번째 행에서 시작해 (N-1)번째 행에서 끝나는 최대 경로 합 구하기

이 튜토리얼에서는 0번째 행의 임의의 셀에서 시작하여 (N-1)번째 행의 임의의 셀에서 끝나는 최대 경로 합을 구하는 프로그램을 C++로 작성해 보겠습니다.

이 문제에서는 N×N 크기의 행렬이 주어지며, 각 셀에서는 아래 세 가지 방향으로만 이동할 수 있습니다.

(i+1, j) : 바로 아래
(i+1, j-1) : 왼쪽 아래 대각선
(i+1, j+1) : 오른쪽 아래 대각선

즉, 0번째 행의 어떤 셀이든 출발점으로 자유롭게 선택한 뒤, 위 규칙에 따라 마지막 행까지 이동하면서 지나간 셀 값들의 합이 최대가 되는 경로를 찾아야 합니다.

접근 방법: 동적 계획법(DP)

가능한 모든 경로를 일일이 탐색하면 시간 복잡도가 기하급수적으로 증가하기 때문에 비효율적입니다. 대신 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

dp[i][j]를 "i번째 행, j번째 열의 셀에 도달했을 때 얻을 수 있는 최대 합"으로 정의합니다.
각 셀은 왼쪽 아래 대각선, 바로 아래, 오른쪽 아래 대각선 위치에서 올 수 있으므로 점화식은 다음과 같습니다.
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + Mat[i][j]
마지막 행(N-1번째 행)의 dp 값들 중 최댓값이 곧 정답이 됩니다.

코드에서는 경계 처리를 단순하게 하기 위해 dp 배열의 열 크기를 N+2로 선언하고 양쪽 끝을 0으로 패딩함으로써, 배열 범위를 벗어나는 경우를 자연스럽게 처리합니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
#define N 4
// 최대 경로 합을 찾는 함수
int MaximumPath(int Mat[][N]) {
    int result = 0 ;
    int dp[N][N+2];
    memset(dp, 0, sizeof(dp));
    // 0번째 행 초기화
    for (int i = 0 ; i < N ; i++)
        dp[0][i+1] = Mat[0][i];
    // 점화식 적용
    for (int i = 1 ; i < N ; i++)
        for (int j = 1 ; j <= N ; j++)
            dp[i][j] = max(dp[i-1][j-1], max(dp[i-1][j], dp[i-1][j+1])) + Mat[i][j-1] ;
    // 마지막 행에서 최댓값 찾기
    for (int i=0; i<=N; i++)
        result = max(result, dp[N-1][i]);
    return result ;
}
int main() {
    int Mat[4][4] = {
        { 4, 2 , 3 , 4 },
        { 2 , 9 , 1 , 10},
        { 15, 1 , 3 , 0 },
        { 16 ,92, 41, 44 }
    };
    cout << MaximumPath ( Mat ) <<endl ;
    return 0;
}

출력 결과

코드 설명

위 예제 행렬에서 최적 경로는 첫 행의 4에서 출발하여 9 → 15 → 92를 순서대로 거치는 경로입니다. 이때 경로의 합은 4 + 9 + 15 + 92 = 120이 됩니다.

이 알고리즘의 시간 복잡도와 공간 복잡도는 모두 O(N²)로, 모든 경로를 탐색하는 브루트 포스 방식(약 O(3ᴺ))에 비해 훨씬 효율적이라는 장점이 있습니다.