[LeetCode] 2257. Count Unguarded Cells in the Grid - Python

 

난이도: 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.

 

문제 예제

---

Example 1:

Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]

Output: 7

Explanation: The guarded and unguarded cells are shown in red and green respectively in the above diagram.

There are a total of 7 unguarded cells, so we return 7.

Example 2:

 

Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]

Output: 4

Explanation: The unguarded cells are shown in green in the above diagram.

There are a total of 4 unguarded cells, so we return 4.

 

제한 사항

---

• 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.

 

솔루션(Solution)

---

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        board = [[0] * n for _ in range(m)]
        
        for i, j in guards:
            board[i][j] = 'G'
        
        for i, j in walls:
            board[i][j] = 'W'
        
        moves = [[1,0], [0,1],[-1,0],[0,-1]]
        
        for i, j in guards:
            for move in moves:
                x, y = i, j
                while True:
                    x += move[0]
                    y += move[1]

                    if 0<=x<m and 0<=y<n and (board[x][y] == 0 or board[x][y] == -1):
                        board[x][y] = -1
                    else:
                        break

        answer = 0
        for i in range(m):
            for j in range(n):
                if board[i][j] == 0:
                    answer += 1
        
        return answer

 

이 문제는 단순히 문제에 나와있는 내용을 그대로 구현하면 되는 문제였다.

 

이 문제를 해결하기 위해 일단 board를 만들어 주어진 m, n에 맞게 0으로 채워주었다.

 

그후 가드에 위치에는 'G', 벽의 위치에는 'W'를 넣어주었다.

 

이제 'G'를 기준으로 상하좌우로 쭉 이동해 조건에 맞으면 그 위치를 -1로 바꿔주었고, 조건에 맞지 않으면 break 문을 통해 다른 위치를 업데이트 해주었다.

 

모든 연산이 끝나면, 마지막에 board에서 0을 가지는 위치를 count해서 정답으로 반환하면 되었다.

 

처음에는 dfs를 써서 풀어야하는 문제인가 했는데, 단순히 문제 그대로 구현만 하면 될 것 같아서 이렇게 풀었던 것 같다.

딱히 어렵지는 않은 문제였다.

---

[LeetCode] 2257. Count Unguarded Cells in the Grid - Python