778. Swim in Rising Water

[zeikar]

Problem link

https://leetcode.com/problems/swim-in-rising-water/

Problem Summary

2차원 배열에 수가 있고 써있는 수만큼의 시간이 지나야 다음 노드로 이동할 수 있다. n-1, n-1에 도착 가능한 최소 시간을 구하는 문제.

Solution

단순 완전 탐색 BFS로 하니 시간 안에 통과는 되지만 매우 느리다.

좀 더 생각을 해보면 시간은 최소 0, 최대 n^2 이므로 이분 탐색으로 가능한 최소 시간을 구한다면 n^2 log(n^2) 으로 구할 수 있다. 다른 방법으로 우선순위 큐를 쓰면 가장 작은 시간부터 탐색을 해나갈 수 있고 이렇게도 n^2 log(n^2) 으로 가능하다.

Source Code

Brute Force BFS (4304 ms)

from typing import List


class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)
        time = grid[0][0]
            
        while True:
            visited = [[False for _ in range(n)] for _ in range(n)]
            que = [(0, 0)]

            while que:
                current = que.pop(0)
                if current[0] == n - 1 and current[1] == n - 1:
                    return time

                for direction in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    next_x = current[0] + direction[0]
                    next_y = current[1] + direction[1]

                    if 0 <= next_x < n and 0 <= next_y < n and not visited[next_x][next_y] \
                            and grid[next_x][next_y] <= time:
                        que.append((next_x, next_y))
                        visited[next_x][next_y] = True

            time += 1

Priority Queue BFS (146 ms)

import heapq
from typing import List


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

        visited = [[False for _ in range(n)] for _ in range(n)]
        que = [(grid[0][0], 0, 0)]
        visited[0][0] = True

        while que:
            current = heapq.heappop(que)
            time = current[0]
            x = current[1]
            y = current[2]

            result = max(result, time)

            if x == n - 1 and y == n - 1:
                return result

            for direction in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                next_x = x + direction[0]
                next_y = y + direction[1]
                if 0 <= next_x < n and 0 <= next_y < n and not visited[next_x][next_y]:
                    heapq.heappush(que, (grid[next_x][next_y], next_x, next_y))
                    visited[next_x][next_y] = True

        return result