[LeetCode] 778. Swim in Rising Water (Swift, Python)

Swim in Rising Water - LeetCode

 

풀이

 우선수위 큐를 활용한 bfs로 해결할 수 있는 문제이다. [0][0]에서 시작해서 [n-1][n-1]로 갈 때까지의 최소 시간을 구해야 한다. 큐에 담을 때 time 값을 해당 좌표의 grid 값을 담아두는데 큐에서 값을 꺼낼 때 time 값이 가장 작은 것을 가져와야 하므로 우선순위 큐를 활용한다. 큐에 있는 값들 중 가장 작은 time을 가진 원소를 꺼내면서 res의 값을 가장 큰 값으로 갱신해준다. 좌표가 [n-1][n-1]이 되면 탐색을 종료하고 갱신된 res값을 리턴해준다.

 

코드

[Swift]

typealias qElement = (time: Int, x: Int, y: Int)
 
class Solution {
    func swimInWater(_ grid: [[Int]]) -> Int {
        let n: Int = grid.count // grid 크기
        var visited: [[Bool]] = Array(repeating: Array(repeating: false, count: n), count: n) // 방문 체크 배열
        let dx: [Int] = [0, 0, 1, -1]
        let dy: [Int] = [1, -1, 0, 0]
        var res: Int = 0
        
        // 해당 위치까지 걸린 시간과 좌표를 담기 위한 큐
        var q: [qElement] = [(grid[0][0], 0, 0)]
        
        while !q.isEmpty {
            q.sort(by: { $0.time < $1.time }) // 걸린 시간이 짧은게 앞에 오도록 정렬
            let front: qElement = q.removeFirst()
            res = max(res, front.time) // 리턴 값 갱신
            visited[front.x][front.y] = true
            
            // [n-1][n-1]에 도달했을 경우 탐색 종료
            if front.x == n-1 && front.y == n-1 {
                break
            }
            
            for i in 0..<4 {
                let nx: Int = front.x + dx[i]
                let ny: Int = front.y + dy[i]
                
                if nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny] {
                    continue
                }
                
                // [nx][ny]까지 갔을 때 걸리는 시간
                q.append((grid[nx][ny], nx, ny))
            }
        }
        
        return res
    }
}
 

 

[Python]

import heapq
 
 
class Solution(object):
    def swimInWater(self, grid):
        visited = [[False] * len(grid) for _ in range(len(grid))] # 방문 체크 리스트
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        n = len(grid) # grid 크기
        res = 0
        
        # 해당 위치까지 걸린 시간과 좌표를 담기 위한 큐
        q = []
        heapq.heappush(q, (grid[0][0], 0, 0))
 
        while q:
            time, x, y = heapq.heappop(q) # 걸린 시간이 짧은 값 pop
            visited[x][y] = True
            res = max(res, time) # 리턴 값 갱신
 
            # [n-1][n-1]에 도달했을 경우 탐색 종료
            if x == n-1 and y == n-1:
                return res
 
            for i in range(4):
                nx = x+dx[i]
                ny = y+dy[i]
 
                if nx < 0 or ny < 0 or nx >= n or ny >= n or visited[nx][ny]:
                    continue
                
                # [nx][ny]까지 갔을 때 걸리는 시간
                heapq.heappush(q, (grid[nx][ny], nx, ny))