C++로 구현하는 행렬 왕복 최대 합 경로 찾기 (동적 계획법)

문제 개요

n×m 크기의 행렬 mat[][]가 주어졌을 때, 왼쪽 위 칸(mat[0][0])에서 출발해 오른쪽 아래 칸(mat[n-1][m-1])까지 이동한 뒤, 다시 출발점으로 되돌아오는 왕복 경로 중 합이 최대가 되는 경로를 찾는 것이 이 문제의 목표입니다.

허용되는 이동 방식

가는 길 (mat[0][0] → mat[n-1][m-1]): 오른쪽(mat[i][j] → mat[i][j+1]) 또는 아래(mat[i][j] → mat[i+1][j])
오는 길 (mat[n-1][m-1] → mat[0][0]): 왼쪽(mat[i][j] → mat[i][j-1]) 또는 위(mat[i][j] → mat[i-1][j])

여기서 중요한 제약 조건은 두 경로가 완전히 동일하면 안 된다는 점입니다. 즉, 가는 경로와 오는 경로는 최소한 하나 이상의 서로 다른 칸을 지나야 합니다.

입력 예시

mat[][] = {
    {1, 2, 4},
    {3, 0, 1},
    {5, -1, -1}
}

출력 결과

15

결과 해설

가는 경로 (mat[0][0] → mat[n-1][m-1]): 1 + 3 + 5 - 1 - 1 = 7
오는 경로 (mat[n-1][m-1] → mat[0][0]): 1 + 4 + 2 + 1 = 8
총합 = 7 + 8 = 15

해결 접근 방법

이 문제를 풀려면 두 개의 경로, 즉 mat[0][0]에서 mat[n-1][m-1]로 가는 경로와 그 반대 방향의 경로를 찾아야 합니다. 하지만 사실 방향만 반대일 뿐 이동 가능한 칸의 집합은 동일하기 때문에, 시작점에서 동시에 출발하는 두 개의 서로 다른 경로를 찾는 방식으로 문제를 단순화할 수 있습니다.

핵심 아이디어

두 경로를 mat[0][0]에서 동시에 진행시키면서, 매 단계마다 각 경로가 오른쪽 또는 아래로 이동하는 네 가지 조합을 모두 고려합니다. 이때 두 경로가 같은 칸에 위치하게 되면 해당 칸의 값은 한 번만 더하고, 서로 다른 칸이라면 각각의 값을 더합니다. 이렇게 하면 '같은 칸을 두 번 세는' 오류를 자연스럽게 방지할 수 있습니다.

또한 재귀 호출 과정에서 동일한 상태(path1x, path1y, path2x)가 반복해서 계산되는 것을 막기 위해 메모이제이션(DP 배열)을 활용합니다. 상태를 3차원 배열 pathSumDP에 저장해 두었다가, 이미 계산된 값이 있으면 즉시 반환함으로써 시간 복잡도를 크게 줄일 수 있습니다.

구현 예제 코드

#include <bits/stdc++.h>
using namespace std;
#define row 3

// 두 경로의 현재 위치 값을 더하는 함수 (같은 칸이면 한 번만)
int CalcNodeDiff(int mat[][row], int path1x, int path1y, int path2x, int path2y) {
    if (path1x == path2x && path1y == path2y) {
        return mat[path1x][path1y];
    }
    return mat[path1x][path1y] + mat[path2x][path2y];
}

// 두 경로의 최대 합을 재귀적으로 계산하는 함수
int calcMaxPathSumOfMat(int mat[][row], int path1x, int path1y, int path2x, int n) {
    static int pathSumDP[5][5][5];
    memset(pathSumDP, -1, sizeof(pathSumDP));
    // 두 경로는 같은 대각선 위에 있으므로 path2y는 path1x, path1y, path2x로 유도 가능
    int path2y = path1x + path1y - path2x;
    int maxPathSum = -10000;

    // 행렬 범위를 벗어나는 경우
    if (path1x >= n || path2x >= n || path1y >= row || path2y >= row)
        return 0;

    // 이미 계산된 상태라면 저장된 값 반환 (메모이제이션)
    if (pathSumDP[path1x][path1y][path2x] != -1)
        return pathSumDP[path1x][path1y][path2x];

    // 두 경로의 이동 조합 4가지를 모두 시도
    maxPathSum = max(maxPathSum,
        calcMaxPathSumOfMat(mat, path1x + 1, path1y, path2x + 1, n) +
        CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
    maxPathSum = max(maxPathSum,
        calcMaxPathSumOfMat(mat, path1x, path1y + 1, path2x, n) +
        CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
    maxPathSum = max(maxPathSum,
        calcMaxPathSumOfMat(mat, path1x, path1y + 1, path2x + 1, n) +
        CalcNodeDiff(mat, path1x, path1y, path2x, path2y));
    maxPathSum = max(maxPathSum,
        calcMaxPathSumOfMat(mat, path1x + 1, path1y, path2x, n) +
        CalcNodeDiff(mat, path1x, path1y, path2x, path2y));

    pathSumDP[path1x][path1y][path2x] = maxPathSum;
    return maxPathSum;
}

int main() {
    int n = 3;
    int mat[n][row] = {
        { 1, 2, 4 },
        { 3, 0, 1 },
        { 5, -1, -1 }
    };
    cout<<"The maximum sum path in a matrix from top to bottom and back is "<<calcMaxPathSumOfMat(mat, 0, 0, 0, n);
    return 0;
}

실행 결과

The maximum sum path in a matrix from top to bottom and back is 15

정리

이 문제의 핵심은 왕복 경로를 '출발점에서 동시에 진행하는 두 경로'로 치환하는 발상과, 두 경로가 같은 칸을 공유할 때 값을 중복 계산하지 않도록 처리하는 것입니다. 여기에 메모이제이션을 결합하면 모든 경로를 일일이 탐색하는 완전 탐색(O(2^(n+m)) 수준)보다 훨씬 효율적인 O(n²×m) 시간 복잡도로 문제를 해결할 수 있습니다.