하나의 행렬이 주어졌다고 가정해 보겠습니다. 우리가 구해야 할 것은 이 행렬 안에 있는 캐비티(cavity)의 개수입니다. 캐비티란 특정 요소를 둘러싸고 있는 모든 인접 요소들이 그 요소보다 큰 값을 가질 때 해당 요소를 가리키는 용어입니다.
예를 들어 다음과 같은 행렬이 있다고 합시다.
| 4 | 5 | 6 |
| 7 | 1 | 5 |
| 4 | 5 | 6 |
정중앙에 있는 값 1은 상·하·좌·우와 네 대각선 방향의 모든 이웃 요소(4, 5, 6, 7)보다 작기 때문에 캐비티에 해당합니다. 따라서 이 행렬에 대한 출력 결과는 1입니다.
알고리즘 접근 방식
핵심 아이디어는 매우 단순합니다. 각 요소의 주변 요소들을 하나씩 검사해서 판단하면 됩니다. 다만 행렬의 가장자리에 있는 요소들은 이웃 중 일부가 존재하지 않기 때문에, 코드에서는 원본 행렬보다 가로세로 2칸씩 큰 배열을 만들고 테두리를 INT_MAX(정수형 최댓값)로 채우는 패딩(padding) 기법을 사용합니다. 이렇게 하면 별도의 경계 조건 검사 없이도 모든 요소를 동일한 방식으로 처리할 수 있습니다.
동작 과정
- 원본 행렬보다 크기가 2씩 큰 새 배열을 만들고, 테두리는
INT_MAX로, 내부에는 원본 행렬의 값을 복사합니다. - 내부의 각 요소에 대해 상·하·좌·우와 네 대각선 방향, 총 8개의 이웃 요소와 값을 비교합니다.
- 8개 이웃이 모두 자신보다 크면 해당 요소를 캐비티로 판정하고 카운트를 1 증가시킵니다.
- 모든 요소에 대한 검사가 끝나면 최종 카운트를 반환합니다.
예제 코드
#include<iostream>
#include<climits>
#define MAX 100
using namespace std;
int numberOfCavities(int array[][MAX], int n) {
int arr[n + 2][n + 2];
int count = 0;
for (int i = 0; i < n + 2; i++) {
for (int j = 0; j < n + 2; j++) {
if ((i == 0) || (j == 0) || (i == n + 1) || (j == n + 1))
arr[i][j] = INT_MAX;
else
arr[i][j] = array[i - 1][j - 1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if ((arr[i][j] < arr[i - 1][j]) && (arr[i][j] < arr[i + 1][j]) && (arr[i][j] < arr[i][j - 1])
&& (arr[i][j] < arr[i][j + 1]) && (arr[i][j] < arr[i - 1][j - 1]) && (arr[i][j] < arr[i + 1][j + 1])
&& (arr[i][j] < arr[i - 1][j + 1]) && (arr[i][j] < arr[i + 1][j - 1])) count++;
}
}
return count;
}
int main() {
int a[][MAX] = { { 4, 5, 6 }, { 7, 1, 5 }, { 4, 5, 6 }};
int n = 3;
cout << "Number of cavities: " << numberOfCavities(a, n);
}실행 결과
Number of cavities: 1
값 1만 유일하게 주변의 모든 요소보다 작기 때문에, 프로그램은 캐비티가 정확히 1개라고 출력합니다.
시간 복잡도
행렬의 모든 요소를 한 번씩 방문하고, 각 요소마다 최대 8개의 이웃을 확인하므로 전체 시간 복잡도는 O(n²)입니다. 패딩된 배열을 추가로 사용하므로 공간 복잡도 역시 O(n²)입니다.