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를 통해서 남아있는 빈칸의 갯수를 반환하는 문제입니다.
Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
Output: 7
연두색 타일이 G가드의 영향을 안받는 타일입니다. 따라서 7을 반환합니다.
Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
Output: 4
제한사항
- 1 ≤ ≤
- 2 ≤ ≤
- 1 ≤ guards.length, walls.length ≤
- 2 ≤ guards.length + walls.length ≤
- 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