[Leetcode 2257번 문제] 2257. Count Unguarded Cells in the Grid

문제 상황

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.

wall은 한칸을 차지하도 GUARD의 시야를 막는다. GUARD는 한칸을 차지하면 상하좌우를 모두 확인한다. 이런 상황에서 사용할 수 있는 칸이 몇개가 있는지를 리턴하라.

입력

• 1 <= m, n <= 105
• 2 <= m * n <= 105
• 1 <= guards.length, walls.length <= 5 * 104
• 2 <= guards.length + walls.length <= m * n
• guards[i].length == walls[j].length == 2
• 0 <= rowi, rowj < m
• 0 <= coli, colj < n
• All the positions in guards and walls are unique.

출력

남은 배열안의 요소 개수

과정

1. 일단 WALL들을 전부 처음 리스트에 반영한다.
2. 이후에 GUARD들을 하나씩 세우면서 위치를 고려한다.
3. 이때 GUARD하나당 4개의 방향을 다닐 수 있기 때문에 내가 오른쪽을 이미 탐사했다면 내 왼쪽에 있는 GUARD가 나를 탐사할 이유가 없다. 그러므로 같은 자리를 탐지하지 않기위해 방향별로 2, 4, 8, 16 비트를 마크시켜놓아 반영해놓는다
4. 모든 작업이 끝나고 남은 칸의 개수를 리턴한다

알고리즘

#define BOUNDARY(x, y, r, c)  0 <= (x) && (x) < (r) && 0 <= (y) && (y) < (c)
class Solution {
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {-1, 1, 0, 0};
public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        vector<vector<int>> table(m, vector<int> (n, 0));
        int answer = m * n;
        for (vector<int> wall : walls)
        {
            table[wall[0]][wall[1]] = 1;
            answer--;
        }

        for (vector<int> guard : guards)
        {
            int pyo = 2;
            for (int i = 0; i < 4; i++)
            {
                int nx = guard[0], ny = guard[1];
                while (BOUNDARY(nx, ny, m, n) && !(table[nx][ny] & (pyo + 1)))
                {
                    if (!table[nx][ny])
                    {
                        answer--;
                    } 
                    table[nx][ny] ^= pyo;
                    nx += dx[i];
                    ny += dy[i];
                }
                pyo *= 2;
            }
        }
        return answer;
    }
};