C++로 폭탄 하나로 죽일 수 있는 최대 적의 수 구하는 프로그램

문제 소개

0, 1, 2 세 가지 값으로 구성된 2차원 행렬이 주어집니다. 여기서 2는 적(enemy), 1은 벽(wall), 0은 빈 칸을 의미합니다. 우리가 구해야 할 것은 폭탄 하나로 죽일 수 있는 최대 적의 수입니다.

폭탄은 설치된 위치에서 같은 행과 같은 열에 있는 모든 적을 제거하지만, 벽을 만나면 더 이상 진행되지 않습니다. 또한 폭탄은 오직 빈 칸(0)에만 설치할 수 있습니다.

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

이 경우 출력은 3입니다. 초록색 칸에 폭탄을 설치하면 최대 3명의 적을 죽일 수 있기 때문입니다.

접근 방법

모든 빈 칸마다 행과 열 전체를 매번 처음부터 탐색하는 방법도 있지만, 이 방식은 시간 복잡도가 O(n² × m²)로 매우 비효율적입니다. 대신 한 번의 순회로 각 위치에서 죽일 수 있는 적의 수를 미리 계산해 두는 최적화 기법을 사용하면 O(n × m) 시간 안에 문제를 해결할 수 있습니다.

핵심 아이디어

• 각 행을 왼쪽에서 오른쪽으로 훑으면서, 현재 위치가 행의 시작이거나 바로 앞 칸이 벽일 때만 해당 구간의 적 수(rowCnt)를 새로 계산합니다.
• 마찬가지로 각 열에 대해서도, 현재 위치가 열의 시작이거나 바로 위 칸이 벽일 때만 해당 구간의 적 수(colCnt[j])를 새로 계산합니다.
• 현재 칸이 빈 칸(0)이라면 rowCnt + colCnt[j] 값을 이용해 정답(ret)을 갱신합니다.

알고리즘 단계

1. ret := 0으로 초기화합니다.
2. n := 그리드의 행 개수, m := 열 개수로 설정합니다.
3. 크기가 m인 배열 colCnt를 정의합니다.
4. i := 0부터 n-1까지 반복합니다.
   • j := 0부터 m-1까지 반복합니다.
     • j가 0이거나 grid[i][j]가 1이면 rowCnt를 초기화한 뒤, 벽을 만나지 않는 범위 내에서 행 방향의 적 수를 계산합니다.
     • i가 0이거나 grid[i][j]가 1이면 colCnt[j]를 초기화한 뒤, 벽을 만나지 않는 범위 내에서 열 방향의 적 수를 계산합니다.
     • grid[i][j]가 0이면 ret을 max(ret, rowCnt + colCnt[j])로 갱신합니다.
5. ret을 반환합니다.

이해를 돕기 위해 다음 구현 예제를 살펴보겠습니다.

예제 코드 (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
   int solve(vector<vector<int>>& 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] == 1) {
               rowCnt = 0;
               int k;
               if (grid[i][j] == 1)
                  k = j + 1;
               else
                  k = j;
               for (; k < m && grid[i][k] != 1; k++) {
                  rowCnt += (grid[i][k] == 2);
               }
            }
            if (!i || grid[i][j] == 1) {
               colCnt[j] = 0;
               int k;
               if (grid[i][j] == 1)
                  k = i + 1;
               else
                  k = i;
               for (; k < n && grid[k][j] != 1; k++) {
                  colCnt[j] += (grid[k][j] == 2);
               }
            }
            if (grid[i][j] == 0) {
               ret = max(ret, rowCnt + colCnt[j]);
            }
         }
      }
      return ret;
   }
};

main(){
   Solution ob;
   vector<vector<int>> v = {
      {0,2,0,0},
      {2,0,1,2},
      {0,2,0,0}};
   cout << (ob.solve(v));
}

입력

{{0,2,0,0},
{2,0,1,2},
{0,2,0,0}}

출력

3

복잡도 분석

시간 복잡도: O(n × m) — 각 행·열 구간의 적 수는 벽을 기준으로 한 번씩만 다시 계산되므로 전체 그리드를 선형 시간에 처리할 수 있습니다.
공간 복잡도: O(m) — 열별 적 수를 저장하는 colCnt 배열이 추가로 필요합니다.