[leetcode] 2257. Count Unguarded Cells in the Grid

안녕하세요. 오늘은 leetcode의 2257. Count Unguarded Cells in the Grid 문제를 풀어봤습니다.

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

 

1. 문제

이 문제에서는 두 수 m, n과 좌표로 이뤄진 두 리스트 guards, walls가 주어집니다.

• m, n은 격자 지도의 세로와 가로를 의미합니다.

m=3, n=4 일 때의 격자 지도

 

• guards는 guard들의 좌표 리스트입니다. guard들은 자신의 좌표에서 상하좌우 방향으로 탐색할 수 있습니다.

(1, 1)에 위치한 guard의 탐색 범위

 

• walls는 wall들의 좌표 리스트입니다. wall은 guard들의 탐색을 막습니다.

(2, 1)에 위치한 wall이 guard의 탐색을 막는 예시

 

문제에서는 guard들이 탐색하지 못하는 칸의 개수를 구해야 합니다.

 

(1, 1)에 guard가 있고 (2, 1)에 wall이 있는 위의 그림에서 guard들이 탐색하지 못하는 칸의 개수는 7개입니다!

 

2. 풀이

제가 시도한 방법은 단순합니다.

 

모든 guard들에 대해서 guard를 만나거나 wall을 만날 때까지 상하좌우 방향으로 계속해서 탐색하는 것이죠.

• 대신에 중복 계산을 막기 위해서 python의 dictionary 자료형을 이용했습니다.

 

하지만 너무 단순했던 걸까요? runtime 효율이 극악입니다 ㅜㅠ

 

풀기만 한 수준...

 

이제 더 개선된 풀이를 찾아봐야겠죠?

+코드

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        num_of_unguarded_cells = m * n
        walls_dict = {}
        visited = {}
        for wall in walls:
            visited[(wall[0], wall[1])] = True
            walls_dict[(wall[0], wall[1])] = True
        for guard in guards:
            visited[(guard[0], guard[1])] = True
            walls_dict[(guard[0], guard[1])] = True
        
        for guard in guards:
            check_up(m, n, guard, walls_dict, visited)
            check_down(m, n, guard, walls_dict, visited)
            check_left(m, n, guard, walls_dict, visited)
            check_right(m, n, guard, walls_dict, visited)
        return num_of_unguarded_cells - len(visited)

def check_up(num_of_row, num_of_cols, guard, walls_dict, visited):
    [row_of_guard, col_of_guard] = guard
    for row in range(row_of_guard-1, -1, -1):
        visited[(row, col_of_guard)] = True
        if (row, col_of_guard) in walls_dict:
            break

def check_down(num_of_row, num_of_cols, guard, walls_dict, visited):
    [row_of_guard, col_of_guard] = guard
    for row in range(row_of_guard+1, num_of_row):
        visited[(row, col_of_guard)] = True
        if (row, col_of_guard) in walls_dict:
            break

def check_left(num_of_row, num_of_cols, guard, walls_dict, visited):
    [row_of_guard, col_of_guard] = guard
    for col in range(col_of_guard-1, -1, -1):
        visited[(row_of_guard, col)] = True
        if (row_of_guard, col) in walls_dict:
            break

def check_right(num_of_row, num_of_cols, guard, walls_dict, visited):
    [row_of_guard, col_of_guard] = guard
    for col in range(col_of_guard+1, num_of_cols):
        visited[(row_of_guard, col)] = True
        if (row_of_guard, col) in walls_dict:
            break