정수로 이루어진 정사각형 배열 A가 주어졌을 때, A를 통과하는 낙하 경로(falling path) 중 합이 가장 작은 경로를 찾는 것이 이 문제의 목표입니다. 낙하 경로란 첫 번째 행의 임의의 원소에서 시작하여, 각 행마다 하나의 원소를 선택하며 아래로 내려가는 경로를 의미합니다. 단, 다음 행에서 선택하는 원소의 열은 바로 위 행에서 선택한 열과 최대 1칸까지만 차이가 나야 한다는 제약 조건이 있습니다.
문제 예시
다음과 같은 3x3 행렬이 주어졌다고 가정해 보겠습니다.
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
이 경우 정답은 12입니다. 가능한 낙하 경로는 [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9], [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,9], [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9] 등 여러 가지가 있으며, 그중 합이 가장 작은 경로는 [1,4,7]로 합이 12입니다.
풀이 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 아래에서부터 위로 거꾸로 올라가면서, 각 위치에서 선택 가능한 세 개의 하단 원소(왼쪽 대각선, 바로 아래, 오른쪽 대각선) 중 최솟값을 현재 값에 더해 누적하는 방식입니다. 구체적인 알고리즘은 다음과 같습니다.
- n := 배열의 크기
- i를 n-2부터 0까지 감소시키며 반복
- j를 0부터 n-1까지 반복
- j - 1 < 0이면 x1 := 무한대(inf), 그렇지 않으면 x1 := matrix[i+1][j-1]
- x2 := matrix[i+1][j]
- j + 1 >= n이면 x3 := 무한대(inf), 그렇지 않으면 x3 := matrix[i+1][j+1]
- matrix[i][j] := matrix[i][j] + min(x1, x2, x3)
- j를 0부터 n-1까지 반복
- ans := 무한대(inf)
- i를 0부터 n-1까지 반복하며 ans := min(ans, matrix[0][i])
- ans 반환
행렬의 마지막에서 두 번째 행부터 시작해 위쪽으로 진행하기 때문에, 모든 연산이 끝난 후 첫 번째 행에 남은 값들 중 최솟값이 곧 전체 경로의 최소 합이 됩니다. 시간 복잡도는 O(n²), 공간 복잡도는 입력 행렬을 그대로 활용하므로 O(1)의 추가 공간으로 처리할 수 있습니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 과정을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& a) {
int n = a.size();
for(int i =n-2;i>=0;i--){
for(int j =0;j<n;j++){
int x1 = j-1<0?INT_MAX:a[i+1][j-1];
int x2 = a[i+1][j];
int x3 = j+1>=n?INT_MAX:a[i+1][j+1];
a[i][j]+= min({x1,x2,x3});
}
}
int ans = INT_MAX;
for(int i =0;i<n;i++){
ans = min(ans,a[0][i]);
}
return ans;
}
};
main(){
vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
Solution ob;
cout <<(ob.minFallingPathSum(v));
}입력
[[1,2,3],[4,5,6],[7,8,9]]
출력
12
코드에서 경계를 벗어나는 경우에는 INT_MAX를 사용해 해당 방향의 선택을 사실상 배제하고, min 함수를 통해 세 방향 중 최솟값을 현재 셀에 누적하는 방식으로 구현되었습니다. 이처럼 바텀업 방식의 DP를 적용하면 별도의 메모이제이션 배열 없이도 문제를 깔끔하게 해결할 수 있습니다.