[leetcode / medium] 3286. Find a Safe Walk Through a Grid - (bfs + dp) (Java)

[leetcode / medium] 3286. Find a Safe Walk Through a Grid

🙋‍♂️ 들어가며

문제에서 m, n <= 50 인데 나는 당연히 2차원 상태관리 DFS가 가능할 것이라고 생각했으나 결국 시간초과가 나서 실패하였다

그 이유로는 당연히 $4^{50 \times 50}$ 이기 때문이다

여기서 왜 4가 나오냐면, 동서남북 방향을 탐색하니 4다

틀린 코드 이후 정답코드에 대한 접근도 설명하겠다

❌ 틀린 코드 (2차원 DFS 상태관리)

class Solution {
    static int row, col;
    static boolean answer;
    static int sr, sc, er, ec;
    static int[][] arr;

    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};

    static boolean can_go_or_not;


    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        
        // 1. 행, 열
        row = grid.size();
        col = grid.get(0).size();
        arr = new int[row][col];

        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                arr[r][c] = grid.get(r).get(c);
            }
        }


        // 2. 값 설정
        sr = 0;
        sc = 0;
        er = row-1;
        ec = col-1;

        // 3. dfs (방문배열 상태관리) 시작
        can_go_or_not = false;
        boolean[][] visited = new boolean[row][col];
        visited[sr][sc] = true;
        if (arr[sr][sc] == 1) {
            health--;
        }
        dfs(sr, sc, visited, health);
        return can_go_or_not;
    }



    // 4. dfs 함수 (상태관리)
    static void dfs(int cr, int cc, boolean[][] visited, int health) {
        // 4-0. 만약 도달했다면 진행하던 모든 탐색 종료
        if (can_go_or_not) return;
        
        // 4-1. 끝에 도착했는데 체력도 1이상이면 true하고 종료
        if (cr == er && cc == ec && health >= 1) {
            can_go_or_not = true;
            return;
        }

        // 4-2. 체력 0이면 죽은거니까 그냥 종료
        if (health == 0) return;

        // 4-3. 이동가능한지 확인
        for (int d = 0; d < 4; d++) {
            int nr = cr + dr[d];
            int nc = cc + dc[d];

            // 4-3-a. 격자범위 벗어나면 skip
            if (nr < 0 || nr >= row || nc < 0 || nc >= col) continue;

            // 4-3-b. 격자 범위안이지만, 방문했다면 skip
            if (visited[nr][nc]) continue;


            // 4-3-c. 격자 범위 안이고, 방문 안했을 때
            // 4-3-d. 다음 좌표가 0이라면?
            if (arr[nr][nc] == 0) {
                // 4-3-e. 방문처리후, dfs
                visited[nr][nc] = true;
                dfs(nr, nc, visited, health);
                // 4-3-f. 방문해제
                visited[nr][nc] = false;
            }
            // 4-3-g. 그게 아니라 다음 좌표가 1이라면?
            else if (arr[nr][nc] == 1) {
                // 4-3-h. 위와 동일하게 처리하지만, 다만 체력은 1을 빼주자
                visited[nr][nc] = true;
                dfs(nr, nc, visited, health-1);
                visited[nr][nc] = false;
            }
        }


    }



}

고민 🤔

이후 2차원 DP를 활용해 -1로 초기화하고 최소값 찾을때처럼, 목숨의 수가 최대일때를 유지할 수 있도록 갱신하는 코드를 작성하였다.

시간복잡도는 아래와 같다

O(N * M)

N, M <= 50 이라 충분

✅ 정답 코드 (2차원 DP + bfs)

import java.util.Queue;
import java.util.LinkedList;


class Solution {
    static int row, col;
    static int[][] DP;
    static int sr, sc, er, ec;

    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};

    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        
        // 1. 행, 열
        row = grid.size();
        col = grid.get(0).size();
        DP = new int[row][col];
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                DP[r][c] = -1;
            }
        }

        // 2. 위치 설정
        sr = 0;
        sc = 0;
        er = row-1;
        ec = col-1;
        
        // 3=1. bfs 생성, 첫 원소넣고 방문 시작
        int start_health = health;
        Queue<int[]> q = new LinkedList<>();

        // 3-2. 만약 첫 시작점이 1이라면,체력 1 깎고 시작
        if (grid.get(0).get(0) == 1) {
            start_health--;
            DP[0][0] = start_health;
        }
        // 3-3. 조기종료
        if (start_health == 0) return false;

        // 3-4. 그 외는 탐색 시작
        q.add(new int[] {sr, sc, start_health});
        
        // 4. 검사
        boolean is_alive = false;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cr = cur[0];
            int cc = cur[1];
            int cur_health = cur[2];

            // 4-1. 끝점 도달했을때
            if (cr == er && cc == ec) {
                // 4-1-a. 현재 체력이 1이상이면
                if (cur_health >= 1) is_alive = true;

                // 4-1-b. 조기종료
                if (is_alive) break;
            }

            // 4-2. 아직 도달 못했으면
            for (int d = 0; d < 4; d++) {
                int nr = cr + dr[d];
                int nc = cc + dc[d];

                // 4-3. 격자 범위 밖이면 skip
                if (nr < 0 || nr >= row || nc < 0 || nc >= col) continue;

                // 4-4. 격자범위에 속해 있을 때
                int cur_status = grid.get(nr).get(nc);

                // 4-6. 다음 체력
                int next_health = cur_health - cur_status;

                // 4-7. 만약 다음체력이 1이상, DP보다 크다면?
                if (next_health >= 1 && next_health > DP[nr][nc]) {
                    DP[nr][nc] = next_health;
                    q.add(new int[] {nr, nc, next_health});
                }

            }

        }


        return is_alive;
    }
}