문제 개요
2차원 격자(grid)가 주어진다고 가정해 봅시다. 각 칸은 다음 세 가지 중 하나입니다.
- 'W' — 벽(Wall)
- 'E' — 적(Enemy)
- '0' — 빈 공간
우리는 하나의 폭탄을 사용해서 제거할 수 있는 최대 적의 수를 구해야 합니다. 폭탄을 설치하면, 해당 지점에서 같은 행과 같은 열에 있는 모든 적이 제거되며, 폭탄의 영향은 벽('W')을 만나는 순간 멈춥니다. 또한 폭탄은 오직 빈 공간('0')에만 설치할 수 있습니다.
예를 들어 아래와 같은 입력이 주어졌다고 합시다.
초록색 위치에 폭탄을 설치하면 3명의 적을 동시에 제거할 수 있으므로, 정답은 3이 됩니다.
접근 방법
이 문제는 단순히 모든 빈 칸마다 행과 열을 매번 새로 탐색하면 O(n²m²)처럼 비효율적일 수 있습니다. 대신 누적 카운트(rowCnt, colCnt)를 활용하면 한 번의 순회로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 어떤 칸에서 왼쪽 방향으로 벽을 만나기 전까지의 적 수를
rowCnt에 저장합니다. - 어떤 칸에서 위쪽 방향으로 벽을 만나기 전까지의 적 수를
colCnt[j]에 저장합니다. - 벽을 만나면 카운트를 초기화하고, 새로운 구간의 카운트를 다시 계산합니다.
구체적인 알고리즘 단계는 다음과 같습니다.
ret := 0으로 초기화합니다.n은 격자의 행 개수,m은 열 개수로 설정합니다.- 크기가 m인 배열
colCnt를 정의합니다. - 행 인덱스 i를 0부터 n-1까지 순회하면서, 열 인덱스 j를 0부터 m-1까지 순회합니다.
- j가 0이거나
grid[i][j]가 'W'라면,rowCnt를 0으로 초기화한 뒤 현재 위치부터 오른쪽으로 벽을 만날 때까지 적('E')의 개수를 셉니다. - i가 0이거나
grid[i][j]가 'W'라면,colCnt[j]를 0으로 초기화한 뒤 현재 위치부터 아래쪽으로 벽을 만날 때까지 적('E')의 개수를 셉니다. grid[i][j]가 '0'(빈 공간)이라면,ret을rowCnt + colCnt[j]와 비교하여 더 큰 값으로 갱신합니다.
- j가 0이거나
- 모든 순회가 끝나면
ret을 반환합니다.
이렇게 하면 각 칸을 상수 번만 처리하므로 전체 시간 복잡도는 O(n × m)이 됩니다.
C++ 구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxKilledEnemies(vector<vector<char>>& grid) {
int ret = 0;
int n = grid.size();
int m = n ? grid[0].size() : 0;
int rowCnt = 0;
vector<int> colCnt(m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!j || grid[i][j] == 'W') {
rowCnt = 0;
int k;
if (grid[i][j] == 'W')
k = j + 1;
else
k = j;
for (; k < m && grid[i][k] != 'W'; k++) {
rowCnt += (grid[i][k] == 'E');
}
}
if (!i || grid[i][j] == 'W') {
colCnt[j] = 0;
int k;
if (grid[i][j] == 'W')
k = i + 1;
else
k = i;
for (; k < n && grid[k][j] != 'W'; k++) {
colCnt[j] += (grid[k][j] == 'E');
}
}
if (grid[i][j] == '0') {
ret = max(ret, rowCnt + colCnt[j]);
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<vector<char>> v = {{'0','E','0','0'},{'E','0','W','E'},{'0','E','0','0'}};
cout << (ob.maxKilledEnemies(v));
}입력
{{'0','E','0','0'},{'E','0','W','E'},{'0','E','0','0'}}출력
3
마무리
이 문제의 핵심은 벽을 기준으로 구간을 나누어 카운트를 재사용하는 것입니다. 행 카운트는 왼쪽에서 오른쪽으로 이동하며 벽을 만날 때만 갱신하고, 열 카운트는 위에서 아래로 이동하며 벽을 만날 때만 갱신함으로써 불필요한 반복 탐색을 제거할 수 있습니다. 덕분에 시간 복잡도를 O(n × m)까지 줄일 수 있으며, 추가 공간 복잡도는 열 개수에 비례하는 O(m)입니다.