Swim in Rising Water

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

Swim in Rising Water - LeetCode

 

각 좌표에 물이 차올라 있어 최소 통과 가능 시간이 정해져 있을 때 최종 좌표까지 도달할 수 있는 최소 시간을 구하는 문제이다. bfs 그래프 문제로 순환하며 풀었으며, 제한 사항을 관리하기 위하여 최소방문 시간 그리드를 이용하였다.

 

특정 좌표 (r,c) 에 대하여 최소 통과 가능 시간은 해당 그리드의 값이고, 실제로 통과한 시간은 다른 그리드를 거쳐 도착했을 때의 최소 시간이다. 다른 그리드를 거쳐 도착했을 때의 시간이 해당 그리드의 최소 시간 이전일 경우 해당 그리드에서 해당 시간까지 대기해야 하기 때문에 Math.max를 이용하여 시간을 체크 해주었다. 또한 다른 경로로 도착했을 때 그보다 빠르게 도착하는 방법이 있을 경우 해당 순환은 불필요하기에 크기 비교를 통하여 경로 필터를 해주었다. 아래는 최종 통과코드이다.

import java.util.*;  
  
public class Solution {  
  
    public int swimInWater(int[][] grid) {  
  
        int m = grid.length;  
        int n = grid[0].length;  
        int[][] minTimes = new int[m][n];  
        for(int i = 0; i < m; i++){  
            Arrays.fill(minTimes[i], Integer.MAX_VALUE);  
        }  
        minTimes[0][0] = grid[0][0];  
        bfs(grid, minTimes);  
  
        return minTimes[m - 1][n - 1];  
    }  
  
    private void bfs(int[][] grid, int[][] minTimes){  
  
        int[] dr = {-1,0,1,0};  
        int[] dc = {0,-1,0,1};  
  
        Queue<int[]> q = new ArrayDeque<>();  
        q.add(new int[]{0,0});  
  
        while(!q.isEmpty()){  
            int[] now = q.poll();  
            int r = now[0];  
            int c = now[1];  
  
            for(int i = 0; i < 4; i++){  
                int nextRow = r + dr[i];  
                int nextCol = c + dc[i];  
                int time = minTimes[r][c];  
  
                if(nextRow >= 0 && nextRow < grid.length  
                        && nextCol >= 0 && nextCol < grid[0].length  
                ){  
                    int nextTime = Math.max(time, grid[nextRow][nextCol]);  
                    if(minTimes[nextRow][nextCol] > nextTime){  
                        minTimes[nextRow][nextCol] = nextTime;  
                        q.add(new int[]{nextRow, nextCol});  
                    }  
                }  
            }  
        }  
    }  
}