[LeetCode 75/Graphs - BFS] 1926 - Nearest Exit from Entrance in Maze / 994 - Rotting Oranges

1926 - Nearest Exit from Entrance in Maze

---

풀이

• 2차원, 정점 (r, c), 상하좌우 이동
• `.`: 이동 가능 / `+`: 벽 (이동 불가)
• 출구: 가장자리에 있는 `.` (!= 시작점)

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

 

• `q.offer(new int[]{r, c, dist})`: (행, 열, 거리)
• `maze[nr][nc] = '+'`: 지나간 곳을 벽으로 바꿈

---

코드

class Solution {
    int m, n;
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};

    int bfs(char[][] maze, int[] entrance) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{entrance[0], entrance[1], 0});

        maze[entrance[0]][entrance[1]] = '+';

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0];
            int c = cur[1];
            int dist = cur[2];

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;

                if (maze[nr][nc] == '+') continue;

                if (nr == 0 || nr == m - 1 || nc == 0 || nc == n - 1) {
                    return dist + 1;
                }

                maze[nr][nc] = '+';
                q.offer(new int[]{nr, nc, dist + 1});
            }
        }

        return -1;
    }

    public int nearestExit(char[][] maze, int[] entrance) {
        m = maze.length;
        n = maze[0].length;

        return bfs(maze, entrance);
    }
}

---

994 - Rotting Oranges

---

풀이

• 0: 빈 공간 / 1: 신선한 오렌지 / 2: 썩은 오렌지
• 상하좌우 이동
• 썩은 오렌지(2) -> 신선한 오렌지(1)로 퍼짐
  => 신선한 오렌지가 썩은 오렌지로 변하는 데 걸리는 최소 시간
  
  • 모든 썩은 오렌지 -> 동시에 시작점으로 넣음
  • `fresh`: 남은 신선한 오렌지 개수 카운트

if (grid[r][c] == 2) {
    q.offer(new int[]{r, c});
}

if (grid[r][c] == 1) fresh++;

 

• `!q.isEmpty() && fresh > 0`: 더 이상 퍼질 게 없거나 다 썩었으면 종료
• 현재 큐에 있는 것들 = 같은 시간(`minute`)에 있는 상태

while (!q.isEmpty() && fresh > 0) {
	int size = q.size();
    
    for (int i = 0; i < size; i++) {
        int[] cur = q.poll();

        for (int d = 0; d < 4; d++) {
            int nr = cur[0] + dr[d];
            int nc = cur[1] + dc[d];

            if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;

            if (grid[nr][nc] != 1) continue;

            grid[nr][nc] = 2;
            fresh--;

            q.offer(new int[]{nr, nc});
        }
    }

    minutes++;
}

---

코드

class Solution {
    int m, n;
    int[] dr = {1, -1, 0, 0};
    int[] dc = {0, 0, 1, -1};

    int bfs(int[][] grid, Queue<int[]> q, int fresh) {
        int minutes = 0;

        while (!q.isEmpty() && fresh > 0) {
            int size = q.size();

            for (int i = 0; i < size; i++) {
                int[] cur = q.poll();

                for (int d = 0; d < 4; d++) {
                    int nr = cur[0] + dr[d];
                    int nc = cur[1] + dc[d];

                    if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;

                    if (grid[nr][nc] != 1) continue;

                    grid[nr][nc] = 2;
                    fresh--;

                    q.offer(new int[]{nr, nc});
                }
            }

            minutes++;
        }

        return fresh == 0 ? minutes : -1;
    }

    public int orangesRotting(int[][] grid) {
        m = grid.length;
        n = grid[0].length;

        Queue<int[]> q = new ArrayDeque<>();
        int fresh = 0;

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 2) {
                    q.offer(new int[]{r, c});
                }

                if (grid[r][c] == 1) fresh++;
            }
        }

        return bfs(grid, q, fresh);
    }
}

---

출처

LeetCode 75 - Study Plan - LeetCode