[LeetCode] 1162 | As Far from Land as Possible

1162 | As Far from Land as Possible
https://leetcode.com/problems/as-far-from-land-as-possible/

 

 

 

 

작성 코드

 

접근 방법

 

1. 0인 grid[x][y]에서 가장 가까운 1 값까지의 거리를 저장해서 max 값을 return

 

import collections

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        counts = -1
        for i in range(len(grid)):
            for j in range(len(grid[0])):                
                if grid[i][j] == 0:
                    q = collections.deque()
                    q.append([i, j, 0, []])
                    while q:
                        x, y, count, path = q.popleft()
                        if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or ([x, y] in path):
                            continue
                            
                        if grid[x][y] == 1:
                            counts = max(counts, count)
                            print(counts)
                            break
                            
                        q.append([x - 1, y, count + 1, path + [[x, y]]])
                        q.append([x + 1, y, count + 1, path + [[x, y]]])
                        q.append([x, y - 1, count + 1, path + [[x, y]]])
                        q.append([x, y + 1, count + 1, path + [[x, y]]])          
        return counts

 

• 전체 요소를 돌면서 grid[x][y] == 0 이면 가장 가까운 1을 찾기 위해 bfs 탐색
• deque 를 이용해 popleft 수행, 상하좌우 값을 append
• grid[x][y] == 1 이면 counts 값과 max 비교하여 갱신, 반복문 종료

• 시간 초과 발생

 

 

이상 코드

 

 

import collections
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        
        if not grid:
            return 0
        rows = len(grid)
        columns = len(grid[0])
        q = collections.deque([(i, j, i, j) for i in range(rows) for j in range(columns) if grid[i][j] == 1])
        visited = set()
        ans = -1

        while q:
            row, column, originalX, originalY = q.popleft()
            if  not 0 <= row < rows or not 0 <= column < columns:
                continue
            if (row, column) not in visited:
                visited.add((row, column))
                if (row, column) != (originalX, originalY):
                    ans = max(ans, abs(row-originalX)+abs(column-originalY))
                for x, y in [(0, 1), (-1, 0), (1, 0), (0, -1)]:
                    newR, newC = row+x, column+y
                    q.append((newR, newC, originalX, originalY))
        return ans
        
# [출처] https://leetcode.com/problems/as-far-from-land-as-possible/discuss/360960/Python-BFS

 

 

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n, res = len(grid), 0
        land = {(i, j) for i, j in product(range(n), range(n)) if grid[i][j]}
        water = {(i, j) for i, j in product(range(n), range(n)) if not grid[i][j]}
        while water:
            if not land: return -1
            land = {(x, y) for i, j in land for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)) if (x, y) in water}
            water -= land
            res += 1
        return res or -1
        
# [출처] https://leetcode.com/problems/as-far-from-land-as-possible/discuss/360960/Python-BFS

 

• product 를 이용하여 모든 요소 경우의 수를 구함