이 글에서는 C++를 이용해 정방행렬(N×N)에서 인접한 네 개 요소의 곱이 가장 커지는 경우를 찾는 방법을 알아봅니다.
여기서 말하는 '인접한 네 개 요소'란 행렬에서 서로 이어진 네 칸을 의미하며, 가로(왼쪽·오른쪽), 세로(위·아래), 대각선 어느 방향이든 가능합니다.
문제 접근 방식
가장 단순하면서도 확실한 방법은 완전 탐색(Brute Force)입니다. 행렬의 모든 칸을 순회하면서, 각 칸을 기준으로 다음 네 방향의 곱을 차례로 계산합니다.
- 가로 방향: 같은 행에서 왼쪽으로 연속된 세 칸과의 곱
- 세로 방향: 같은 열에서 위쪽으로 연속된 세 칸과의 곱
- 주대각선 방향: 왼쪽 위로 연속된 세 칸과의 곱
- 부대각선 방향: 오른쪽 위로 연속된 세 칸과의 곱
곱을 계산할 때마다 현재까지의 최댓값과 비교하여 더 크면 갱신합니다. 이때 행렬의 경계를 벗어나지 않도록 인덱스 조건을 반드시 확인해야 합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
const int n = 5;
// 최대 곱을 찾는 함수
int FindMaxProduct(int arr[][n], int n) {
int max = 0, result;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 가로 방향 검사
if ((j - 3) >= 0) {
result = arr[i][j] * arr[i][j - 1] * arr[i][j - 2] * arr[i][j - 3];
if (max < result)
max = result;
}
// 세로 방향 검사
if ((i - 3) >= 0) {
result = arr[i][j] * arr[i - 1][j] * arr[i - 2][j] * arr[i - 3][j];
if (max < result)
max = result;
}
// 주대각선 방향 검사
if ((i - 3) >= 0 && (j - 3) >= 0) {
result = arr[i][j] * arr[i - 1][j - 1] * arr[i - 2][j - 2] * arr[i - 3][j - 3];
if (max < result)
max = result;
}
// 부대각선 방향 검사
if ((i - 3) >= 0 && (j + 3) < n) {
result = arr[i][j] * arr[i - 1][j + 1] * arr[i - 2][j + 2] * arr[i - 3][j + 3];
if (max < result)
max = result;
}
}
}
return max;
}
int main() {
int arr[][5] = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 1},
{2, 3, 4, 5, 6},
{7, 8, 9, 1, 0},
{9, 6, 4, 2, 3}
};
cout << FindMaxProduct(arr, n);
return 0;
}
실행 결과
3024
결과 분석
예제 행렬에서 두 번째 행의 6, 7, 8, 9가 가로로 인접한 네 요소이며, 곱은 6 × 7 × 8 × 9 = 3024로 전체 최댓값이 됩니다. 세로나 대각선 방향의 어떤 조합도 이 값보다 크지 않으므로 3024가 최종 결과로 반환됩니다.
시간 복잡도
행렬의 모든 칸을 한 번씩 방문하고, 각 칸에서 상수 번의 곱셈과 비교만 수행하므로 시간 복잡도는 O(n²)입니다. 추가 배열을 사용하지 않으므로 공간 복잡도는 O(1)입니다.
참고: 음수가 포함된 경우
위 코드는 최댓값을 0으로 초기화하기 때문에, 행렬의 모든 요소가 음수인 경우에는 잘못된 결과(0)를 반환할 수 있습니다. 음수 입력도 고려해야 한다면 max 변수를 INT_MIN으로 초기화하는 것이 안전합니다.