C++로 그리드에서 조명된 셀의 개수 구하는 방법

문제 설명

h × w 크기의 격자가 주어졌다고 가정해 보겠습니다. 격자의 각 칸에는 전구 또는 장애물이 놓여 있을 수 있습니다. 전구가 있는 칸은 자기 자신과 상하좌우 네 방향의 칸들을 비추며, 빛은 장애물에 막히지 않는 한 계속 퍼져 나갑니다. 반면 장애물이 있는 칸은 조명될 수 없으며, 전구의 빛이 다른 칸까지 도달하는 것을 차단합니다.

따라서 전구의 좌표가 담긴 배열 bulb와 장애물의 좌표가 담긴 배열 obstacle이 주어졌을 때, 격자에서 조명되는 칸의 총 개수를 구해야 합니다.

입력 예시

예를 들어 h = 4, w = 4, bulb = {{1, 1}, {2, 2}, {3, 3}}, obstacle = {{0, 0}, {2, 3}}이 입력으로 주어지면 출력은 13이 됩니다.

해결 접근 방법

이 문제는 각 행과 열을 정방향·역방향으로 한 번씩 스캔하는 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

전구 위치는 grid에 1로, 장애물 위치는 2로 표시합니다.
각 행을 왼쪽→오른쪽, 오른쪽→왼쪽으로 스캔하면서 전구를 만나면 '빛이 켜짐' 플래그를 설정하고, 장애물을 만나면 플래그를 해제합니다.
같은 방식으로 각 열을 위→아래, 아래→위로 스캔합니다.
스캔 중 플래그가 켜져 있는 칸은 조명되는 칸이므로 check 배열에 기록합니다.
마지막으로 check가 false인 칸의 개수를 전체 칸 수에서 빼면 정답이 됩니다.

알고리즘 단계

문제를 해결하기 위해 다음 단계를 따릅니다.

bulbSize := bulb의 크기, blockSize := obstacle의 크기로 초기화합니다.
2차원 배열 grid를 정의하고, 전구 위치에는 1, 장애물 위치에는 2를 저장합니다.
result := h * w로 초기화합니다.
2차원 배열 check를 정의합니다.
각 행 i에 대해 왼쪽에서 오른쪽으로, 이어서 오른쪽에서 왼쪽으로 스캔하며 조명 여부를 check에 OR 연산으로 누적합니다.
각 열 j에 대해 위에서 아래로, 이어서 아래에서 위로 스캔하며 같은 작업을 수행합니다.
모든 칸을 순회하며 check[i][j]가 false인 경우 result에서 1씩 감소시킵니다.
result를 반환합니다.

C++ 구현 예제

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

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

int solve(int h, int w, vector<pair<int, int>> bulb, vector<pair<int, int>> obstacle){
   int bulbSize = bulb.size();
   int blockSize = obstacle.size();
   vector<vector<int>> grid(h, vector<int>(w, 0));
   for (int i = 0; i < bulbSize; i++) {
      int x = bulb[i].first;
      int y = bulb[i].second;
      grid[x][y] = 1;
   }
   for (int i = 0; i < blockSize; i++) {
      int x = obstacle[i].first;
      int y = obstacle[i].second;
      grid[x][y] = 2;
   }
   int result = h * w;
   vector<vector<bool>> check(h, vector<bool>(w, 0));
   for (int i = 0; i < h; i++) {
      bool gd = 0;
      for (int j = 0; j < w; j++) {
         if (grid[i][j] == 2)
            gd = 0;
         if (grid[i][j] == 1)
            gd = 1;
         check[i][j] = check[i][j] | gd;
      }
      gd = 0;
      for (int j = w - 1; j >= 0; j--) {
         if (grid[i][j] == 2)
            gd = 0;
         if (grid[i][j] == 1)
            gd = 1;
         check[i][j] = check[i][j] | gd;
      }
   }
   for (int j = 0; j < w; j++) {
      bool k = 0;
      for (int i = 0; i < h; i++) {
         if (grid[i][j] == 2)
            k = 0;
         if (grid[i][j] == 1)
            k = 1;
         check[i][j] = check[i][j] | k;
      }
      k = 0;
      for (int i = h - 1; i >= 0; i--) {
         if (grid[i][j] == 2)
            k = 0;
         if (grid[i][j] == 1) k = 1;
         check[i][j] = check[i][j] | k;
      }
   }
   for (int i = 0; i < h; i++)
      for (int j = 0; j < w; j++)
         result -= !check[i][j];
   return result;
}
int main() {
   int h = 4, w = 4;
   vector<pair<int, int>> bulb = {{1, 1}, {2, 2}, {3, 3}}, obstacle = {{0, 0}, {2, 3}};
   cout<< solve(h, w, bulb, obstacle);
   return 0;
}

입력

4, 4, {{1, 1}, {2, 2}, {3, 3}}, {{0, 0}, {2, 3}}

출력

복잡도 분석

이 알고리즘의 시간 복잡도는 O(h × w)입니다. 각 행과 열을 최대 두 번씩만 스캔하기 때문입니다. 공간 복잡도 역시 grid와 check 배열을 저장해야 하므로 O(h × w)입니다.