2023.02.10 Today's Challenge

fabichoi 2023. 2. 10. 23:45

https://leetcode.com/problems/as-far-from-land-as-possible/

As Far from Land as Possible - LeetCode

As Far from Land as Possible - Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or wa

leetcode.com

BFS로 풀면 되는 문제!

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = deque()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    q.append((i, j, 0))

        if not q or len(q) == m*n:
            return -1
        
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        while q:
            i, j, d = q.popleft()
            for x, y in dirs:
                ii, jj = i + x, j + y
                if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] == 0:
                    grid[ii][jj] = 1
                    q.append((ii, jj, d+1))
        
        return d