[leetcode] 2257. Count Unguarded Cells in the Grid #2

안녕하세요. 오늘은 이전에 풀었던 2257. Count Unguarded Cells in the Grid 문제를 다시 풀어보겠습니다.

극악의 runtime 효율!

• 참고: https://goodahn.tistory.com/252

 

1. 개선된 문제 풀이

이전에 풀었던 방법의 시간복잡도는 O(max(m, n) * guard 수) 입니다.

그런데 'max(m, n) * guard 수'는 최대 10^9까지 커질 수 있습니다!

 

그래서 알고리즘의 속도가 느린 것이었죠.

• 격자지도의 모든 점을 확인하는 것보다는 모든 guard에 대해서만 확인하는 것이 효율적이라고 생각했지만 문제 조건이 그렇지 않았습니다...
• guard의 수만큼 격자지도를 중복으로 검사하는 것이 효율성에 많은 영향을 미친 것 같더라고요

 

새로운 방법은 격자지도의 모든 점을 확인하는 방법입니다.

아래 그림과 같이 오른쪽, 왼쪽, 위쪽, 아래쪽으로 한번씩 훑으면서 격자지도의 좌표가 guard들에 의해 탐색되었는지 확인합니다.

guard 수에 영향을 덜 받는 검사 방법

 

그런데... runtime 효율성이 생각보다 많이 개선되지는 않았습니다.

 

다음에는 leetcode의 솔루션과 다른 풀이가 있는지 찾아봐야겠네요!

 

+ 코드

class Solution:
    def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
        grid_map = [[0] * n for _ in range(m)]
        UNGUARDED = 0
        GUARDED = 1
        GUARD = 2
        WALL = 3

        for wall in walls:
            grid_map[wall[0]][wall[1]] = WALL
        for guard in guards:
            grid_map[guard[0]][guard[1]] = GUARD
        
        # check right direction
        for row_idx in range(m):
            is_guarded = UNGUARDED
            for col_idx in range(n):
                if grid_map[row_idx][col_idx] == GUARD:
                    is_guarded =  GUARDED
                elif grid_map[row_idx][col_idx] == WALL:
                    is_guarded = UNGUARDED
                elif is_guarded == GUARDED:
                    grid_map[row_idx][col_idx] = GUARDED

        # check left direction
        for row_idx in range(m):
            is_guarded = UNGUARDED
            for col_idx in range(n)[::-1]:
                if grid_map[row_idx][col_idx] == GUARD:
                    is_guarded =  GUARDED
                elif grid_map[row_idx][col_idx] == WALL:
                    is_guarded = UNGUARDED
                elif is_guarded == GUARDED:
                    grid_map[row_idx][col_idx] = GUARDED

        # check up direction
        for col_idx in range(n):
            is_guarded = UNGUARDED
            for row_idx in range(m)[::-1]:
                if grid_map[row_idx][col_idx] == GUARD:
                    is_guarded =  GUARDED
                elif grid_map[row_idx][col_idx] == WALL:
                    is_guarded = UNGUARDED
                elif is_guarded == GUARDED:
                    grid_map[row_idx][col_idx] = GUARDED

        # check down direction
        for col_idx in range(n):
            is_guarded = UNGUARDED
            for row_idx in range(m):
                if grid_map[row_idx][col_idx] == GUARD:
                    is_guarded =  GUARDED
                elif grid_map[row_idx][col_idx] == WALL:
                    is_guarded = UNGUARDED
                elif is_guarded == GUARDED:
                    grid_map[row_idx][col_idx] = GUARDED
        
        result = 0
        for row_idx in range(m):
            for col_idx in range(n):
                if grid_map[row_idx][col_idx] == UNGUARDED:
                    result += 1
        return result