문제 링크

내 코드

바로 그냥 중복 방문했다가 TLE $\rightarrow$ 이후에 마땅히 좋은 아이디어가 없었다.

• ms, MB

class Solution {
public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        vector board(m, vector(n, 0));

        for(auto wall : walls) { 
            int x = wall[0], y = wall[1];
            board[x][y] = 2; // wall
        }

        for(auto guard : guards) {
            int guardX = guard[0], guardY = guard[1];

            board[guardX][guardY] = 1;

            for(int d{};d<4;++d) {
                int x = guardX, y = guardY;
                while(1) {
                    int nx = x + "0211"[d] - '1', ny = y + "1102"[d] - '1';
                    
                    if(nx < 0 || nx >= m || ny < 0 || ny >= n) break;
                    if(board[nx][ny] == 2) break;
                    
                    x = nx, y = ny;
                    board[nx][ny] = 1;
                }
            }
        }

        int answer{};
        for(auto row : board) {
            for(auto col : row) {
                if(!col) ++answer;
            }
        }

        return answer;
    }
};

밑에 Approach 1 참고해서..

• guard를 미리 순회해서 채워 넣는 경우 시간 내에 통과 가능..!
• 81ms, 186.49MB

class Solution {
public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        vector board(m, vector(n, 0));
        // guard를 초기에 한 번 더 미리 채워 넣기(중복 방문 방지)
        for(auto& guard : guards) {
            int guardX = guard[0], guardY = guard[1];
            board[guardX][guardY] = 1; // guard
        }

        for(auto& wall : walls) { 
            int x = wall[0], y = wall[1];
            board[x][y] = 2; // wall
        }

        for(auto& guard : guards) {
            for(int d{};d<4;++d) {
                int x = guard[0], y = guard[1];
                while(1) {
                    int nx = x + "0211"[d] - '1', ny = y + "1102"[d] - '1';
                    
                    if(nx < 0 || nx >= m || ny < 0 || ny >= n) break;
                    if(board[nx][ny] == 2) break; // wall
                    if(board[nx][ny] == 1) break; // guard
                    
                    x = nx, y = ny;
                    board[nx][ny] = 3;
                }
            }
        }

        int answer{};
        for(auto row : board) {
            for(auto col : row) {
                if(!col) ++answer;
            }
        }

        return answer;
    }
};

Solution

Approach 1: Iterative Simulation

• 63ms, 172.17MB
• Complexity
  • Let m be the number of rows, n the number of columns, g be the number of guards in the guards list, and w be the number of walls in the walls list.
  • Time Complexity: $O(m \cdot n + g \cdot (m + n) + m \cdot n) = O(m \cdot n + g \cdot (m + n))$
  • Space Complexity: $O(m \cdot n)$

class Solution {
public:
    const int UNGUARDED = 0;
    const int GUARDED = 1;
    const int GUARD = 2;
    const int WALL = 3;

    void markguarded(int row, int col, vector<vector<int>>& grid) {
        // Traverse upwards
        for (int r = row - 1; r >= 0; r--) {
            if (grid[r][col] == WALL || grid[r][col] == GUARD) break;
            grid[r][col] = GUARDED;
        }
        // Traverse downwards
        for (int r = row + 1; r < grid.size(); r++) {
            if (grid[r][col] == WALL || grid[r][col] == GUARD) break;
            grid[r][col] = GUARDED;
        }
        // Traverse leftwards
        for (int c = col - 1; c >= 0; c--) {
            if (grid[row][c] == WALL || grid[row][c] == GUARD) break;
            grid[row][c] = GUARDED;
        }
        // Traverse rightwards
        for (int c = col + 1; c < grid[row].size(); c++) {
            if (grid[row][c] == WALL || grid[row][c] == GUARD) break;
            grid[row][c] = GUARDED;
        }
    }

    int countUnguarded(int m, int n, vector<vector<int>>& guards,
                       vector<vector<int>>& walls) {
        vector<vector<int>> grid(m, vector<int>(n, UNGUARDED));

        // Mark guards' positions
        for (const auto& guard : guards) {
            grid[guard[0]][guard[1]] = GUARD;
        }

        // Mark walls' positions
        for (const auto& wall : walls) {
            grid[wall[0]][wall[1]] = WALL;
        }

        // Mark cells as guarded by traversing from each guard
        for (const auto& guard : guards) {
            markguarded(guard[0], guard[1], grid);
        }

        // Count unguarded cells
        int count = 0;
        for (const auto& row : grid) {
            for (const auto& cell : row) {
                if (cell == UNGUARDED) count++;
            }
        }
        return count;
    }
};

Approach 2: Recursive Way

• 60ms, 172.24MB
• Complexity
  • Let m be the number of rows, n the number of columns, g be the number of guards in the guards list, and w be the number of walls in the walls list.
  • Time Complexity: $O(m \cdot n + g \cdot (m + n) + m \cdot n)$
  • Space Complexity: $O(m \cdot n)$

class Solution {
public:
    const int UNGUARDED = 0;
    const int GUARDED = 1;
    const int GUARD = 2;
    const int WALL = 3;

    void recurse(int row, int col, vector<vector<int>>& grid, char direction) {
        if (row < 0 || row >= grid.size() || col < 0 ||
            col >= grid[row].size() || grid[row][col] == GUARD ||
            grid[row][col] == WALL) {
            return;
        }
        grid[row][col] = GUARDED;  // Mark cell as guarded
        if (direction == 'U') recurse(row - 1, col, grid, 'U');  // Up
        if (direction == 'D') recurse(row + 1, col, grid, 'D');  // Down
        if (direction == 'L') recurse(row, col - 1, grid, 'L');  // Left
        if (direction == 'R') recurse(row, col + 1, grid, 'R');  // Right
    }

    int countUnguarded(int m, int n, vector<vector<int>>& guards,
                       vector<vector<int>>& walls) {
        vector<vector<int>> grid(m, vector<int>(n, UNGUARDED));

        // Mark guards' positions
        for (const auto& guard : guards) {
            grid[guard[0]][guard[1]] = GUARD;
        }

        // Mark walls' positions
        for (const auto& wall : walls) {
            grid[wall[0]][wall[1]] = WALL;
        }

        // Mark cells as guarded by traversing from each guard
        for (const auto& guard : guards) {
            recurse(guard[0] - 1, guard[1], grid, 'U');  // Up
            recurse(guard[0] + 1, guard[1], grid, 'D');  // Down
            recurse(guard[0], guard[1] - 1, grid, 'L');  // Left
            recurse(guard[0], guard[1] + 1, grid, 'R');  // Right
        }

        // Count unguarded cells
        int count = 0;
        for (const auto& row : grid) {
            for (const auto& cell : row) {
                if (cell == UNGUARDED) count++;
            }
        }
        return count;
    }
};