[LeetCode] 1162. As Far from Land as Possible

- Problem

1162. As Far from Land as Possible

- 내 풀이 1 (BFS, TLE)

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        def bfs(y, x):
            q = collections.deque([[y, x, 0]])
            visited = set()
            visited.add((y, x))

            while q:
                y, x, dist = q.popleft()
                if grid[y][x]:
                    return dist

                for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    ny = y + dy
                    nx = x + dx

                    if 0 <= ny < N and 0 <= nx < N and (ny, nx) not in visited:
                        visited.add((ny, nx))
                        q.append([ny, nx, dist+1])
                            
            return -1

        N = len(grid)
        answer = -1

        for i in range(N):
            for j in range(N):
                if not grid[i][j]:
                    answer = max(bfs(i, j), answer)

        return -1 if answer == 0 else answer

- 결과

- 내 풀이 2 (Optimized BFS)

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        def bfs():
            dist = 0

            while q:
                for _ in range(len(q)):
                    y, x = q.popleft()

                    for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                        ny = y + dy
                        nx = x + dx

                        if 0 <= ny < N and 0 <= nx < N and not grid[ny][nx]:
                            q.append((ny, nx))
                            grid[ny][nx] = 1
                
                dist += 1
            
            return dist
            
        N = len(grid)
        q = deque(((i, j) for i in range(N) for j in range(N) if grid[i][j]))
        answer = bfs()
        
        return answer - 1 if answer > 1 else -1

- 결과