문자로 구성된 행렬 mat[][]가 있다고 가정해 보겠습니다. 이 행렬에는 세 종류의 문자가 등장합니다. Z는 좀비(zombie), P는 식물(plant), *는 아무것도 없는 빈 땅(bare land)을 의미합니다. 좀비는 자신과 인접한 칸에 있는 식물을 공격할 수 있으며, 우리의 목표는 좀비의 공격으로부터 안전한 식물 셀이 몇 개인지 구하는 것입니다.
예를 들어 다음과 같은 행렬이 주어졌다고 합시다.
이 행렬에서 좀비에게 공격받지 않는 안전한 식물은 단 2개뿐입니다.
문제 해결 접근 방법
풀이 자체는 매우 직관적입니다. 행렬을 처음부터 끝까지 한 칸씩 순회하면서, 현재 칸이 식물('P')이라면 그 주변 8방향(상·하·좌·우 및 네 대각선)에 좀비('Z')가 있는지 검사합니다. 8방향 어디에도 좀비가 없다면 이 식물은 안전하므로 결과 카운트를 1 증가시킵니다.
알고리즘 동작 순서
- 이중 반복문으로 행렬의 모든 칸을 순회합니다.
- 현재 칸이
'P'(식물)인지 확인합니다. - 식물이라면
isZombie()헬퍼 함수를 호출해 주변 8방향(자기 자신 포함)에 좀비가 있는지 검사합니다. isZombie()는 좌표가 행렬 범위를 벗어나거나 해당 칸이'Z'가 아니면false를 반환하므로, 행렬 경계(테두리) 처리도 자연스럽게 해결됩니다.- 모든 방향에서 좀비가 발견되지 않으면 안전한 식물이므로
count를 증가시킵니다. - 순회가 끝나면
count를 반환합니다.
참고로 코드에서는 자기 자신 칸 (i, j)도 함께 검사하는데, 이 칸은 이미 'P'이므로 항상 false가 반환되어 결과에는 영향을 주지 않습니다.
C++ 구현 예제
#include<iostream>
using namespace std;
// 해당 좌표에 좀비('Z')가 있는지 확인하는 함수
bool isZombie(int i, int j, int r, int c, string mat[]) {
if (i < 0 || j < 0 || i >= r || j >= c || mat[i][j] != 'Z')
return false;
return true;
}
// 안전한 식물 셀의 개수를 세는 함수
int countSafeCells(string matrix[], int row, int col) {
int i, j, count = 0;
for (i = 0; i < row; i++) {
for (j = 0; j < col; j++) {
if (matrix[i][j] == 'P') {
if (!isZombie(i - 1, j - 1, row, col, matrix) && !isZombie(i - 1, j, row, col, matrix)
&& !isZombie(i - 1, j + 1, row, col, matrix) && !isZombie(i, j - 1, row, col, matrix)
&& !isZombie(i, j, row, col, matrix) && !isZombie(i, j + 1, row, col, matrix)
&& !isZombie(i + 1, j - 1, row, col, matrix) && !isZombie(i + 1, j, row, col, matrix)
&& !isZombie(i + 1, j + 1, row, col, matrix)) {
count++;
}
}
}
}
return count;
}
int main() {
string mat[] = { "**P*", "Z***", "*P**", "***P" };
int row = sizeof(mat) / sizeof(mat[0]);
int col = mat[0].length();
cout << "안전한 셀의 개수: " << countSafeCells(mat, row, col);
}
실행 결과
안전한 셀의 개수: 2
복잡도 분석
행렬의 크기를 R×C라고 할 때, 모든 칸을 한 번씩 방문하고 각 칸에서 최대 9번의 상수 시간 검사를 수행하므로 시간 복잡도는 O(R×C)입니다. 또한 별도의 추가 배열이나 자료구조를 사용하지 않으므로 공간 복잡도는 O(1)입니다.