[2257] Count Unguarded Cells in the Grid | Biweekly Contest 77 Medium

yoongyum·2022년 5월 5일
0

코딩테스트 🧩

목록 보기
34/47
post-thumbnail

🔎 문제설명

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.

대충 한글 요약:

2차원 배열에 G, W , 빈칸 이렇게 3종류로 채워져 있습니다.
G는 가드인데 상하좌우 4방향을 W를 만나기 전까지 빈칸을 없애버립니다.

배치된 G,W를 통해서 남아있는 빈칸의 갯수를 반환하는 문제입니다.

Example 1

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

연두색 타일이 G가드의 영향을 안받는 타일입니다. 따라서 7을 반환합니다.

Example 2

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

제한사항

  • 1 ≤ m,nm, n10510^5
  • 2 ≤ mnm * n10510^5
  • 1 ≤ guards.length, walls.length ≤ 51045 * 10^4
  • 2 ≤ guards.length + walls.length ≤ mnm * 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.



근데 이문제의 특이한 점은 m과n의 최대 크기가 100,000인데 두개를 곱한 값의 최대값도 100,000입니다.

따라서 생각보다 타일의 크기가 크지 않을 것 같다는 생각을 해서 DFS를 썼습니다.

라고 생각했는 데 풀다보니까 DFS까지 안써도 됬습니다.

🧊 파이썬 코드

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        tile = [[0]*n for i in range(m)]
        
        # 0은 공백
        # 1은 가드
        # 2는 벽
        # 3은 가드가 왔던 곳
        for x, y in guards:
            tile[x][y] = 1
        
        for x, y in walls:
            tile[x][y] = 2
            
        dx = [1,-1,0,0]
        dy = [0,0,1,-1]
        
        
        for x, y in guards: 
            for d in range(4): 
                i = x + dx[d]
                j = y + dy[d]
                while i >= 0 and i < m and j >= 0 and j < n: 
                    if tile[i][j] in (0,3): #빈칸이나 가드가 지나간 곳이면 계속 진행
                        tile[i][j] = 3
                        i += dx[d]
                        j += dy[d]
                    else : break
               
        return sum(t.count(0) for t in tile) #tile에 빈칸 갯수 반환

제한조건을 잘 읽어봐야합니다.ㅎㅎ
m*n <= 100,000 인걸 모르면 DFS로도 풀생각을 못합니다.


🍸 다른사람 풀이

DFS풀이를 가져왔습니다. DFS가 조금 더 시간효율은 좋습니다.

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        H, W = m, n
        M = [[0] * W for _ in range(H)]
        ans = (H * W) - len(guards) - len(walls)

        # free = 0
        # wall = 1
        # guard = 2
        # guarded = 3

        for r, c in walls: M[r][c] = 1
        for r, c in guards: M[r][c] = 2
            
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
            
        def dfs(y, x, d):
            nonlocal ans
            if 0 <= y < H and 0 <= x < W:
                cell = M[y][x]
                if cell == 2 or cell == 1:
                    return
                
                if cell == 0:
                    ans -= 1
                    M[y][x] = 3
                
                dy, dx = y + d[0], x + d[1]
                dfs(dy, dx, d)        
            
        for guard in guards:
            r, c = guard
            for d in dirs:
                dy, dx = r + d[0], c + d[1]
                dfs(dy, dx, d)    
            
        return ans

0개의 댓글