C++로 찾는 행렬 최대 가중치 경로: 마지막 행의 요소로 끝나는 경로 탐색

문제 개요

이번 문제에서는 정수 n과 각 칸(cell)의 가중치를 담고 있는 n×n 크기의 행렬이 주어집니다. 목표는 마지막 행의 어느 요소든 도착점으로 삼을 수 있는 최대 가중치 경로를 찾는 프로그램을 작성하는 것입니다.

경로 탐색은 항상 좌측 상단(0,0)에서 시작하며, 이동할 수 있는 방향은 아래쪽과 대각선 두 가지뿐입니다. 왼쪽으로 이동하는 것은 허용되지 않습니다.

예시로 이해하기

입력 −

n = 3
Mat[3][3] = {
    {4, 3, 1}
    {5, 8, 9}
    {6, 7, 2}}

출력 −

19

설명 −

가능한 모든 경로는 다음과 같습니다.
Path1: 4+5+6 = 15
Path2: 4+8+7 = 19
Path3: 4+8+2 = 12
Path4: 4+5+7 = 16

네 가지 경로 중 가장 큰 가중치를 가진 경로는 Path2이며, 그 값은 19입니다.

해결 접근 방식

가장 단순한 방법은 가능한 모든 경로를 전부 계산한 뒤 서로 비교하는 것입니다. 하지만 n이 커질수록 경로의 수가 급격히 늘어나기 때문에 매우 비효율적인 접근입니다.

훨씬 효과적인 해법은 동적 계획법(Dynamic Programming)을 활용하는 것입니다. 이 문제는 같은 하위 문제가 반복해서 등장하는 중첩(overlapping) 유형에 해당하기 때문입니다. 시작점에서 출발하면 원하는 결과를 만들어낼 수 있는 n개의 분기가 존재합니다.

먼저, 행렬의 각 칸에 도달할 때까지 누적된 최대 가중치를 저장하는 별도의 행렬(sumMat)을 생성합니다. 이후 마지막 행에서 최댓값을 찾아 출력하면 정답을 구할 수 있습니다.

구현 예제

문제를 해결하는 C++ 프로그램은 다음과 같습니다.

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000;
int maxCost(int matrix[][MAX], int N) {
   int sumMat[N][N];
   memset(sumMat, 0, sizeof(sumMat));
   int maxSum = 0;
   sumMat[0][0] = matrix[0][0];
   for (int i=1; i<N; i++)
      sumMat[i][0] = matrix[i][0] + sumMat[i-1][0];
   for (int i=1; i<N; i++)
   for (int j=1; j<i+1&&j<N; j++)
      sumMat[i][j] = matrix[i][j] + max(sumMat[i-1][j-1], sumMat[i-1][j]);
   for (int i=0; i<N; i++)
      if (maxSum < sumMat[N-1][i]) maxSum = sumMat[N-1][i];
      return maxSum;
}
int main(){
   int mat[MAX][MAX] ={
      {5 , 6 , 1 },
      {2 , 11 , 10 },
      {15, 3 , 2 }};
   int N = 3;
   cout<<"Maximum Path Sum for top-left cell to last row is : "<<maxCost(mat, N)<<endl;
   return 0;
}

실행 결과

Maximum Path Sum for top-left cell to last row is : 22