[코테연습] 2257. Count Unguarded Cells in the Grid

https://leetcode.com/problems/count-unguarded-cells-in-the-grid/description/?envType=daily-question&envId=2024-11-21

문제타입

Array
Matrix
Simulation

문제 분석

• 문제:
  • m x n 크기의 격자에서 경비원과 벽의 위치가 주어졌을 때, 감시되지 않은 셀의 수를 구합니다.
• 경비원의 감시 규칙:
  • 경비원은 상, 하, 좌, 우 네 방향으로 감시할 수 있습니다.
  • 감시 범위는 벽(W)이나 다른 경비원(G)이 나타날 때까지 제한됩니다.
• 입력:
  • m, n: 격자의 크기
  • guards: 경비원 위치 리스트
  • walls: 벽 위치 리스트
• 출력:
  • 감시되지 않은 셀의 수를 정수로 반환합니다.

---

문제 풀이

• 아이디어:
  • 격자(grid)를 생성하고, W(벽), G(경비원), V(감시된 영역)를 표시합니다.
  • 각 경비원에서 네 방향으로 감시 범위를 탐색합니다.
  • 탐색 후 남은 점(.)의 수를 카운트합니다.

풀이 단계:

1. 초기화:
   • 격자(grid)를 점(.)으로 초기화합니다.
   • 벽과 경비원의 위치를 각각 W, G로 표시합니다.
2. 경비원 감시 처리:
   • 각 경비원 위치에서 네 방향으로 탐색.
   • 벽(W)이나 다른 경비원(G)이 나타날 때 탐색 종료.
   • 감시 가능한 셀(.)을 V로 변경.
3. 결과 계산:
   • 감시되지 않은 셀(.)의 개수를 세어 반환합니다.

방향 탐색:

• 네 방향(상, 하, 좌, 우) 탐색을 위해 방향 벡터를 사용:
  • dx = [1, -1, 0, 0] (하, 상)
  • dy = [0, 0, 1, -1] (우, 좌)

 

> java

 

class Solution {
    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
        char[][] maps = new char[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maps[i][j] = '.';
            }
        }
        for (int i = 0; i < walls.length; i++) {
            int x = walls[i][0];
            int y = walls[i][1];
            maps[x][y] = 'W';
        }
        for (int i = 0; i < guards.length; i++) {
            int x = guards[i][0];
            int y = guards[i][1];
            maps[x][y] = 'G';
        }

        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};

        for (int[] guard : guards) {
            int x = guard[0];
            int y = guard[1];

            for (int i = 0; i < 4; i++) {
                int nx = x;
                int ny = y;
                while(true) {
                    nx+=dx[i]; //해당 방향으로 계속 이동
                    ny+=dy[i]; //해당 방향으로 계속 이동
                    if (nx >= m || ny >= n || nx < 0 || ny < 0 || maps[nx][ny] == 'W' || maps[nx][ny] == 'G') {
                        break;
                    }
                    if (maps[nx][ny] == '.') {
                        maps[nx][ny]= 'V';
                    }

                }
            }
        }
        int total = 0;
        for (char[] map : maps) {
            for (char c : map) {
                if (c == '.'){
                    total+=1;
                }
            }
        }
        return total;
    }

    
}

 

 

> python

 

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        maps = [['.' for _ in range(n)] for _ in range(m)]
        for i in range(len(walls)) :
            maps[walls[i][0]][walls[i][1]] = 'W'
        for i in range(len(guards)) :
            maps[guards[i][0]][guards[i][1]] = 'G'
        dx = [1,-1,0,0]
        dy = [0,0,1,-1]
        for guard in guards :
            x = guard[0]
            y = guard[1]
            for i in range(4) :
                nx = x
                ny = y
                while True :
                    nx += dx[i]
                    ny += dy[i]
                    if nx >= m or ny >= n or nx < 0 or ny < 0 or maps[nx][ny] == 'W' or maps[nx][ny] == 'G' :
                        break
                    if maps[nx][ny] == '.' :
                        maps[nx][ny] = 'V'

        total = 0
        for row in range(len(maps)) :
            for col in range(len(maps[row])) :
                if maps[row][col] == '.': 
                    total+=1
        return total