1. 문제 소개

2257. Count Unguarded Cells in the Grid

2. 나의 풀이법

처음에는 guard의 시선을 하나하나 생각한 계산을 사용했다.
시간복잡도는 처음 그리드를 생성한 시간과 guard별로 한 번 순회를 반복해 $O(mn + |guards|·(m+n))$인데, m과 n의 크기가 작아서 짧은 시간이 걸린 것 같다.

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        grid = [[1] * n for _ in range(m)]
        
        for g_x, g_y in guards:
            grid[g_x][g_y] = "G"

        for w_x, w_y in walls:
            grid[w_x][w_y] = "W"
        
        for g_x, g_y in guards:
            u, d, l, r = g_y - 1, g_y + 1, g_x - 1, g_x + 1

            while u >= 0 and grid[g_x][u] not in ("W", "G"):
                grid[g_x][u] = 0
                u -= 1

            while d < n and grid[g_x][d] not in ("W", "G"):
                grid[g_x][d] = 0
                d += 1

            while l >= 0 and grid[l][g_y] not in ("W", "G"):
                grid[l][g_y] = 0
                l -= 1

            while r < m and grid[r][g_y] not in ("W", "G"):
                grid[r][g_y] = 0
                r += 1

        return sum(row.count(1) for row in grid)

3. 다른 풀이법

시간복잡도는 같지만 풀이가 미세하게 다르다. 그러나 방법은 똑같다.

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:

        # Step 1: Initialize the grid
        # 0 → unguarded, 1 → guarded, 2 → occupied (guard or wall)
        grid = [[0] * n for _ in range(m)]

        # Step 2: Mark guards and walls on the grid
        for r, c in guards:
            grid[r][c] = 2
        for r, c in walls:
            grid[r][c] = 2

        # Step 3: Define directions (up, right, down, left)
        dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]

        # Step 4: Simulate guard vision (ray propagation)
        for gr, gc in guards:
            for dr, dc in dirs:
                r, c = gr + dr, gc + dc
                while 0 <= r < m and 0 <= c < n and grid[r][c] < 2:
                    grid[r][c] = 1  # mark as guarded
                    r += dr
                    c += dc

        # Step 5: Count unguarded cells
        count = sum(cell == 0 for row in grid for cell in row)

        # Step 6: Return the result
        return count

4. 결론

처음 생각한 풀이가 문제의 제약속에서는 효율적인 풀이여서 다행이다.
다른 방법이 있는 지는 조금 궁금하다.