3286. Find a Safe Walk Through a Grid

https://leetcode.com/problems/find-a-safe-walk-through-a-grid/description/

 

You are given an m x n binary matrix grid and an integer health.
You start on the upper-left corner (0, 0) and would like to get to the lower-right corner (m - 1, n - 1).
You can move up, down, left, or right from one cell to another adjacent cell as long as your health remains positive.
Cells (i, j) with grid[i][j] = 1 are considered unsafe and reduce your health by 1.
Return true if you can reach the final cell with a health value of 1 or more, and false otherwise.

 

m x n 크기의 2차원 배열이 주어지고 (0,0) 좌표에서 무사히 (m-1,n-1)까지 도달할 수 있는지 판단하는 문제였다. 추가적으로 health 값이 주어지고, 배열에서 1인 칸을 밟으면 -1 감소된다. 마지막 칸에 도달했을 때 health 값이 1 이상이라면 true, 아니라면 false를 리턴했다.

원본 배열 말고 각 칸마다 health 상태를 저장하는 int [][] val을 만들어 BFS로 탐색하도록 구현하였다.

1인 칸을 만났을 때는 이전 칸의 -1,

0인 칸을 만났을 때는 이전 칸의 상태를 그대로 유지하도록 하였다.

 

if (board[nx][ny] == 1) nxtHealth = val[x][y] - 1;
else nxtHealth = val[x][y];

 

하지만, 위의 예제에서 탐색을 진행했을 때 val 값이 되는 칸이 존재했고 체력이 0 이하가 되는 경로는 유효하지 않으므로 탐색을 중단해야 할 로직이 필요했다. 

if (nxtHealth < 1) continue;

 

또한, visited로 방문 체크를 진행했는데 만약에 다음 칸에 더 높은 체력으로 도달할 수 있는 경우의 수가 있다면 해당 경우의 수를 선택해야하는 추가 조건이 필요했다.

if (nxtHealth > val[nx][ny]) {
    val[nx][ny] = nxtHealth;
    q.add(new int[]{nx,ny});
}

 

 

1. 체력 값이 1미만이 되는 경우 탐색 중지
2. 이동하려는 칸의 체력 값이 현재 값보다 큰 경우에만 탐색을 진행.(아니라면 최악의 경우의 수로 빠져서 도달할 수 있음에도 도달하지 못하는 경우의 수가 발생)

이 두가지 조건을 놓쳐서 풀지 못했다. 

 

 

전체 코드

class Solution {
    // (0,0)에서 (m-1,n-1)까지 출발
    // health값이 주어지고, 칸이 1을 밟으면 health - 1. 
    // 최종점에서 health가 1이상이면 true, 아니라면 false를 반환.

    int [][] board;
    int [][] val;
    int [] dx = {1,0,-1,0};
    int [] dy = {0,1,0,-1};
    int n, m;
    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        n = grid.size();
        m = grid.get(0).size();

        board = new int[n][m];
        val = new int[n][m];

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < grid.get(i).size(); j++) {
                board[i][j] = grid.get(i).get(j);
            }
        }

        if (board[0][0] == 1) val[0][0] = health - 1;
        else val[0][0] = health;
        
        bfs(health);

        // for(int i = 0; i < n; i++){
        //     for(int j = 0; j < m; j++) {
        //         System.out.print(val[i][j] + " ");
        //     }
        //     System.out.println();
        // }

    
        return val[n-1][m-1] >= 1;
    }

    public void bfs(int health) {
        Queue<int []> q = new LinkedList<>();
        q.add(new int[]{0,0});
        while(!q.isEmpty()) {
            int [] cur = q.poll();
            int x = cur[0];
            int y = cur[1];

            int nxtHealth = 0;
            for(int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
                int tmp_val = 0;
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                
                // 다음 지점이 1이라면, 현재값 -1
                if (board[nx][ny] == 1) nxtHealth = val[x][y] - 1;
                else nxtHealth = val[x][y]; 

                if (nxtHealth < 1) continue;
                if (nxtHealth > val[nx][ny]) {
                    val[nx][ny] = nxtHealth;
                    q.add(new int[]{nx,ny});
                }
            }
        }
    }
}