778. Swim in Rising Water (Array, Binary Search, Depth-First Search, Breadth-First Search, Union Find, Heap (Priority Queue), Matrix)

링크 - https://leetcode.com/problems/swim-in-rising-water/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Hard

Intuition

1) Heap

우리는 매 좌표마다 주변의 cell값들을 heap에 넣어서 가장 적은 값의 좌표로 이동할 수 있다는 점을 사용할 수 있다. 여기서 visited이름의 set()을 사용해서 이미 방문한 좌표는 다시 방문하지 않도록 한다. 왜냐하면 이미 방문했다는 것은 그 다음의 길도 이미 탐험이 끝났기 때문이다.

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)

        visited = {(0, 0)}
        heap = [(grid[0][0], 0, 0)]
        ans = 0
        while heap:
            t, r, c = heapq.heappop(heap)
            ans = max(ans, t)
            if r == c == n-1:
                return ans

            for new_r, new_c in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):
                if 0 <= new_r < n and 0 <= new_c < n and (new_r, new_c) not in visited:
                    heapq.heappush(heap, (grid[new_r][new_c], new_r, new_c))
                    visited.add((new_r, new_c))

Time Complexity: O(N^2 * logN) 우리는 N^2의 좌표를 돌면서, 그 안에서 logN의 heap operation을 하기 때문이다.

Space Complexity: O(N^2) 힙의 최대 크기는 grid만큼 커질 수 있다.

2) Binary Search and DFS

우리는 T가 grid[0][0]과 n*n사이에 있다는 점을 알고있다. 따라서 이를 사용해 dfs를 돌리면서 binary search를 통해 답을 찾을 수 있다.

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)

        def dfs(t):
            queue = [(0,0)]
            visited = {(0,0)}
            while queue:
                r, c = queue.pop()
                if r == c == n-1:
                    return True

                for new_r, new_c in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):
                    if 0 <= new_r < n and 0 <= new_c < n and (new_r, new_c) not in visited and grid[new_r][new_c] <= t:
                        queue.append((new_r, new_c))
                        visited.add((new_r, new_c))

            return False

        left, right = grid[0][0], n*n
        while left < right:
            mid = (left + right) // 2
            if not dfs(mid):
                left = mid + 1
            else:
                right = mid

        return left

Time Complexity: O(N^2 * logN) 우리는 N^2의 dfs를 하면서, 매번 logN의 binary search를 하기 때문이다.

Space Complexity: O(N^2) 힙의 최대 크기는 grid만큼 커질 수 있다.