문제 정의
2차원 격자(grid)가 주어집니다. 각 칸은 세 가지 값 중 하나입니다. 벽('W'), 적('E'), 또는 빈 공간('0')입니다. 우리가 작성해야 할 함수는 폭탄 하나를 사용했을 때 최대 몇 명의 적을 처치할 수 있는지를 반환해야 합니다.
폭탄이 설치된 지점을 기준으로 같은 행과 같은 열에 있는 모든 적을 처치합니다. 단, 벽을 만나면 더 이상 진행되지 않습니다. 벽은 너무 튼튼해서 폭탄으로도 파괴할 수 없기 때문입니다.
또한 한 가지 조건이 더 있습니다. 폭탄은 반드시 빈 칸('0')에만 설치할 수 있다는 점입니다.
입력 예시
const arr = [ ['0', 'E', '0', '0'], ['E', '0', 'W', 'E'], ['0', 'E', '0', '0'] ];
위 입력에 대한 함수의 출력 결과는 다음과 같습니다.
const output = 3;
출력 설명
[1, 1] 위치에 폭탄을 설치하면 같은 행과 열에 있는 적 3명을 동시에 처치할 수 있으며, 이것이 어떤 위치에 놓아도 달성할 수 있는 최댓값입니다.
효율적인 해결 접근 방식
모든 빈 칸마다 상하좌우를 매번 전부 탐색하면 비효율적입니다. 대신 다음 두 가지 값을 활용하면 격자를 한 번만 순회하면서(O(m×n)) 답을 구할 수 있습니다.
- rows 변수: 현재 칸과 같은 행에서, 직전 벽 이후로 만난 적의 수를 저장합니다. 행의 시작이거나 바로 앞 칸이 벽인 경우 0으로 초기화한 뒤 다시 계산합니다.
- cols 배열: 각 열별로, 직전 벽 이후로 만난 적의 수를 저장합니다. 첫 번째 행이거나 바로 위 칸이 벽인 경우 해당 열의 값을 초기화한 뒤 다시 계산합니다.
이렇게 하면 이미 계산해 둔 값을 재활용할 수 있어 불필요한 반복 탐색을 제거할 수 있습니다.
구현 코드
const arr = [
['0', 'E', '0', '0'],
['E', '0', 'W', 'E'],
['0', 'E', '0', '0']
];
const killEnemy = (arr = []) => {
let m = arr.length;
let n = m > 0 ? arr[0].length : 0;
let result = 0, rows = 0;
const cols = [];
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (j === 0 || arr[i][j-1] === 'W') {
rows = 0;
for (let k = j; k < n && arr[i][k] != 'W'; ++k)
if (arr[i][k] === 'E')
rows += 1;
}
if (i === 0 || arr[i-1][j] === 'W') {
cols[j] = 0;
for (let k = i; k < m && arr[k][j] != 'W'; ++k)
if (arr[k][j] === 'E')
cols[j] += 1;
}
if (arr[i][j] === '0' && rows + cols[j] > result)
result = rows + cols[j];
}
}
return result;
};
console.log(killEnemy(arr));실행 결과
코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
3