(Python3) - LeetCode (Medium) 2257. Count Unguarded Cells in the Grid

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

2차원 배열을 순회하는 것을 구현해본 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. m행 n열 2차원 배열 grid를 선언 후 wall은 'W'로 guard는 'G'로 표기해놓습니다.

 

2. m행 n열 2차원 배열 checked를 선언 후 모두 0으로 초기화합니다.

 

3. 4방향 동서남북에 대한 dr, dc를 선언 후 방향에 맞게 선언해줍니다.

 

4. deque 변수 dp를 선언해 줍니다.

 

5. 정답 변수 answer를 선언 후 0으로 초기화합니다.

📔 풀이과정

1. guards를 순회하며 각 위치에 해당하는 grid를 'G'로 표시합니다. 또한 이 위치의 checked또한 1로 표기합니다.

 

2. walls를 순회하며 마찬가지로 grid와 checked를 갱신합니다.

 

3. dq에 원소가 있는 동안 while loop를 수행하며 다음을 진행합니다.

  3-1. 현재 위치 r행 c열을 dq에서 꺼내서 저장합니다.

  3-2. 4방향에 대해 다음을 진행합니다.

    3-2-1. current_row, current_col을 r, c에 각각 저장해줍니다.

    3-2.2. while loop를 수행하며 한 방향으로 쭉 가주면서 다음 좌표 nr, nc를 구해서 범위가 넘거나 벽을 만나면 break해줍니다. 만약 유효한 grid 위라면 checked 배열을 1로 갱신해주고 current_row, current_col값을 다음 좌표로 갱신해줍니다.

 

4. checked의 원소를 2차원으로 순회하며 0값인 원소를 세어 answer에 저장합니다.

📔 정답 출력 | 반환

answer를 반환합니다.

---

📕 Code

📔 Python3

from collections import deque
class Solution:
    
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        grid = [[0]*n for _ in range(m)]
        checked = [[0]*n for _ in range(m)]
        dr = [0,0,1,-1]
        dc = [1,-1,0,0]
        dq = deque()
        answer = 0
        for g in guards:
            dq.append((g[0], g[1]))
            checked[g[0]][g[1]] = 1
            grid[g[0]][g[1]] = 'G'
        for w in walls:
            grid[w[0]][w[1]] = 'W'
            checked[w[0]][w[1]] = 1

        while dq:
            r, c = dq.popleft()
            for i in range(4):
                current_row = r
                current_col = c
                while True:
                    nr = current_row + dr[i]
                    nc = current_col + dc[i]
                    if not (0<=nr<m and 0<=nc<n):
                        break
                    if grid[nr][nc] == 'W' or grid[nr][nc] == 'G':
                        break
                    checked[nr][nc] = 1
                    current_row = nr
                    current_col = nc
                    
        for i in range(m):
            for j in range(n):
                if checked[i][j] == 0:
                    answer += 1
        return answer

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.