[LeetCode] 2257. Count Unguarded Cells in the Grid

https://leetcode.com/problems/count-unguarded-cells-in-the-grid/description/

leetcode - Count Unguarded Cells in the Grid

문제 유형: 행렬, 완전 탐색

문제 난이도: Medium

 

문제

You are given two integers m and n representing a 0-indexed m x n grid. You are also given two 2D integer arrays guards and walls where guards[i] = [rowi, coli] and walls[j] = [rowj, colj] represent the positions of the ith guard and jth wall respectively.

A guard can see every cell in the four cardinal directions (north, east, south, or west) starting from their position unless obstructed by a wall or another guard. A cell is guarded if there is at least one guard that can see it.

Return the number of unoccupied cells that are not guarded.

 

두 개의 정수 m과 n을 받습니다. m은 행의 수, n은 열의 수입니다.

gurads[i] = [rowi, coli], rowi, coli에 위치한 경비원의 정보가 배열로 주어집니다.

wall[i]도 똑같은 형식으로 위치정보가 주어집니다.

 

경비원은 동서남북 방향을 지킬 수 있습니다.

각 방향의 벽이나 다른 경비원의  전 칸까지 지킬 수 있습니다.

 

보호되지 않는 땅의 넓이를 구하시오.

 

풀이

최적화를 해보겠다고 이런저런 일을 다 했는데, 부질없었다..

그냥 각 경비원 칸에서 동서남북으로 영역을 확장하면 되는 것이었다.

 

각 경비원에 대해서, dfs또는 bfs로 4가지 방향으로만 2D배열에 마킹하면서 영역을 확장해나가면 된다.

아무런 마킹되지 않느 부분의 넓이를 구하면 그게 정답이다.

 

코드

C++

class Solution {
public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        vector<vector<char>> grid(m, vector<char>(n, 0));
        for(auto &w : walls) grid[w[0]][w[1]] = 'W';
        for(auto &g : guards) grid[g[0]][g[1]] = 'G';

        vector<int> d = {-1, 0, 1, 0};
        for(const auto &g : guards) {
            int x = g[0];
            int y = g[1];

            for(int i = 0; i < 4; ++i) {
                int nx = x + d[i];
                int ny = y + d[(i + 5) % 4];

                while(nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] != 'W' && grid[nx][ny] != 'G') {
                    grid[nx][ny] = 'V';
                    nx += d[i];
                    ny += d[(i + 5) % 4];
                }
            }
        }

        int count = 0;
        for(auto row : grid) {
            for(int cell : row) {
                if(cell == 0) ++count;
            }
        }
        return count;
    }
};