C++로 구현하는 NxN 그리드 최소 합 하강 경로 알고리즘

문제 설명

• 크기가 NxN인 정수 행렬 A가 주어집니다. 이때 A를 통과하는 하강 경로(falling path)의 최소 합을 구하는 것이 목표입니다.
• 하강 경로는 첫 번째 행의 임의의 원소에서 시작하여 마지막 행의 원소에서 끝납니다.
• 경로는 다음 행마다 하나의 원소를 선택하며, 다음 행에서 선택하는 원소의 열은 이전 행에서 선택한 열과 최대 1칸 차이까지만 허용됩니다. 즉, 바로 아래, 왼쪽 아래 대각선, 오른쪽 아래 대각선 위치 중 하나만 선택할 수 있습니다.

예시

N = 2이고 행렬이 다음과 같다면:
{
    {5, 10},
    {25, 15}
}
출력은 20이 됩니다. 원소 5와 15를 선택하기 때문입니다.

이 문제는 동적 계획법(Dynamic Programming)을 사용하면 효율적으로 해결할 수 있습니다. 기본 아이디어는 마지막 행부터 위쪽으로 거슬러 올라가며, 각 칸에 "해당 칸에서 시작해 마지막 행까지 내려갈 때 얻을 수 있는 최소 합"을 저장하는 것입니다. 각 칸의 새로운 값은 자신의 원래 값에, 바로 아래 행의 세 후보 위치(바로 아래, 왼쪽 아래, 오른쪽 아래) 중 최솟값을 더한 것입니다. 경계에 있는 열의 경우 존재하지 않는 방향은 제외하고 계산합니다. 모든 행을 처리한 뒤 첫 번째 행의 값들 중 가장 작은 값이 곧 정답이 됩니다.

이 방식의 시간 복잡도는 O(N²), 공간 복잡도는 입력 행렬을 그대로 활용하므로 추가 공간 없이 O(1)로 해결할 수 있다는 장점이 있습니다.

구현 예제

#include <bits/stdc++.h>
#define MAX 2
using namespace std;
int getMinSumPath(int matrix[MAX][MAX]) {
    for (int row = MAX - 2; row >= 0; --row) {
        for (int col = 0; col < MAX; ++col) {
            int val = matrix[row + 1][col];
            if (col > 0) {
                val = min(val, matrix[row +1][col - 1]);
            }
            if (col + 1 < MAX) {
                val = min(val, matrix[row +1][col + 1]);
            }
            matrix[row][col] = matrix[row][col] +val;
        }
    }
    int result = INT_MAX;
    for (int i = 0; i < MAX; ++i)
    result = min(result, matrix[0][i]);
    return result;
}
int main() {
    int matrix[MAX][MAX] = {
        {5, 10},
        {25, 15},
    };
    cout << "Minimum sum path = " << getMinSumPath(matrix)
    << endl;
    return 0;
}

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

출력 결과

Minimum sum path = 20