문제 설명
정사각형 격자 형태의 배열 arr가 주어집니다. '비영 이동(non-zero shift) 낙하 경로'란 각 행에서 정확히 하나의 원소를 선택하되, 인접한 두 행에서 선택한 원소가 같은 열에 위치하지 않도록 하는 경로를 의미합니다. 이 조건을 만족하는 모든 낙하 경로 중에서 원소들의 합이 가장 작은 값을 찾는 것이 이번 문제의 목표입니다.
예시로 이해하기
입력이 [[1,2,3],[4,5,6],[7,8,9]]인 경우를 살펴보겠습니다. 만들 수 있는 낙하 경로는 [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9]입니다. 이 중 합이 가장 작은 경로는 [1,5,7]이며 합계는 13입니다. 따라서 정답은 13이 됩니다.
알고리즘 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 셀에 대해 '바로 윗행에서 자신과 같은 열을 제외한 원소들 중 최솟값'을 빠르게 구하는 것입니다. 이를 위해 왼쪽 방향 누적 최솟값(leftMin)과 오른쪽 방향 누적 최솟값(rightMin) 두 개의 보조 배열을 사용합니다.
구체적인 풀이 단계는 다음과 같습니다.
- n := 행의 개수, m := 열의 개수로 설정합니다.
- i := 1부터 n 미만까지 반복하며 다음을 수행합니다.
- 크기가 m인 leftMin, rightMin 배열을 정의합니다.
- leftMin[0] := arr[i-1][0]으로 초기화한 뒤, j := 1부터 m 미만까지 leftMin[j] := min(leftMin[j-1], arr[i-1][j])를 계산합니다.
- rightMin[m-1] := arr[i-1][m-1]로 초기화한 뒤, j := m-2부터 0 이상까지 역순으로 rightMin[j] := min(arr[i-1][j], rightMin[j+1])를 계산합니다.
- j := 0부터 m 미만까지 각 열에 대해 다음을 적용합니다.
- leftVal := (j-1이 0 이상이면 leftMin[j-1], 아니면 1000000)
- rightVal := (j+1이 m 미만이면 rightMin[j+1], 아니면 1000000)
- arr[i][j] := arr[i][j] + min(leftVal, rightVal)
- ans := 무한대로 초기화한 후, 마지막 행 arr[n-1]의 모든 값 중 최솟값을 구합니다.
- ans를 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 과정을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& arr) {
int n = arr.size();
int m = arr[0].size();
for (int i = 1; i < n; i++) {
vector<int> leftMin(m);
vector<int> rightMin(m);
leftMin[0] = arr[i - 1][0];
for (int j = 1; j < m; j++) {
leftMin[j] = min(leftMin[j - 1], arr[i - 1][j]);
}
rightMin[m - 1] = arr[i - 1][m - 1];
for (int j = m - 2; j >= 0; j--) {
rightMin[j] = min(arr[i - 1][j], rightMin[j + 1]);
}
for (int j = 0; j < m; j++) {
int leftVal = (j - 1) >= 0 ? leftMin[j - 1] : 1000000;
int rightVal = (j + 1) < m ? rightMin[j + 1] : 1000000;
arr[i][j] += min(leftVal, rightVal);
}
}
int ans = INT_MAX;
for (int i = 0; i < m; i++)
ans = min(ans, arr[n - 1][i]);
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
cout << (ob.minFallingPathSum(v));
}입력
{{1,2,3},{4,5,6},{7,8,9}}출력
13
복잡도 분석 및 마무리
이 풀이는 각 행마다 세 번의 선형 순회를 수행하므로 전체 시간 복잡도는 O(n×m)입니다. 공간 복잡도는 길이 m짜리 보조 배열 두 개를 사용하므로 O(m)입니다. 매 셀마다 윗행 전체를 일일이 탐색하는 O(n×m²) 방식과 비교하면, 누적 최솟값 배열을 활용한 이 접근법이 훨씬 효율적이라는 점이 핵심 포인트입니다.