LeetCode 994(Rotting Orange, java)

0. 문제

https://leetcode.com/problems/rotting-oranges/

Rotting Oranges - LeetCode

 

 

1. 문제 설명

- 문제에서 이중 배열(grid)이 주어진다.

- 이중 배열에는 빈 공간(= 0), 신선한 오렌지(= 1), 상한 오렌지(= 2)와 같은 3가지 값이 저장되어있다.

- 상한 오렌지에 인접한 신선한 오렌지는 1분이 지날 때마다 상한다.

- 인접한 오렌지 중 상한 오렌지가 존재하지 않는다면 오렌지는 상하지 않는다.

- 모든 오렌지가 상한다면 상할때 까지의 최소 시간을 반환한다.

- 신선한 오렌지가 1개라도 존재한다면 -1을 반환한다.

 

 

2. 문제 해설

a) 첫 번째 접근

- 문제를 처음 읽어보면 굉장히 어려운 문제라는 생각이 든다.

- 인접한 오렌지가 상한 오렌지인지 확인해야하고, 오렌지가 상할 때마다 시간을 체크해야 한다.

- 더불어, 상한 오렌지가 2개라면 2개의 상한 오렌지를 동시에 추적해야 한다.

 

- 도무지 어떻게 접근해야 할지 막막할 것이다. 

- 그러나 관점을 조금 바꾸면 굉장히 쉬운 문제라는 것을 알 수 있다.

 

b) 두 번째 접근

- 이 문제는 전형적인 BFS 문제다.

- 탐색의 기준을 상한 오렌지로부터 신선한 오렌지를 오염시키는 것으로 설정한다.

- 이렇게 접근하면 문제가 굉장히 쉬워진다.

 

c) 세 번째 접근

- Queue를 이용하여 상한 오렌지의 위치를 기록한다.

- 그리고 상한 오렌지를 기준으로 인접한 신선한 오렌지를 오염시킨다.

- 오염된 오렌지의 좌표는 Queue에 저장되어 다음 탐색에서 방문한다.

- 전형적인 Queue 자료구조를 이용한 BFS 탐색이다. 

 

d) 네 번째 접근

- 마지막에 확인해야 할 것이 있다.

- 인접한 오렌지의 오염을 모두 확인하더라도 동떨어져 있는 오렌지가 존재할 수 있다.

- 그러므로 이중 배열 내부에 신선한 오렌지가 남아있는지 확인해야 한다.

 

- 그러나 전체 이중 배열을 한번 더 탐색하는 것은 효율적이지 않다.

- 그러므로 자료구조를 하나 만들어서 신선한 오렌지의 위치를 따로 저장해놓는다.

- 이렇게 저장해놓은 신선한 오렌지의 좌표를 마지막에 검증하면 된다.

 

- 다음 코드를 보면서 이해해보자. 

 

 

3. 정답 코드

class Solution {
    public int orangesRotting(int[][] grid) {
        
        int row = grid.length;
        int col = grid[0].length;
        int time = 0;
        
        Queue<int[]> que = new LinkedList<>();
        List<int[]> fresh = new ArrayList<>();
        
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(grid[i][j] == 2) { // 상한 오렌지의 위치를 저장
                    que.offer(new int[]{i, j});
                }
                
                if(grid[i][j] == 1) { // 신선한 오렌지의 위치를 저장
                    fresh.add(new int[]{i, j});
                }
            }
        }
        
        while(!que.isEmpty()) { // BFS 탐색
            int initial = que.size();
            
            while(initial > 0) {
                initial--;
                
                int[] position = que.poll();
                int r = position[0];
                int c = position[1];
                
                // 인접 노드 탐색(상하좌우)
                if(r > 0 && grid[r - 1][c] == 1) {
                    que.offer(new int[]{r - 1, c});
                    grid[r - 1][c] = 2;
                }
                
                if(c > 0 && grid[r][c - 1] == 1) {
                    que.offer(new int[]{r, c - 1});
                    grid[r][c - 1] = 2;
                }
                
                if(r < row - 1 && grid[r + 1][c] == 1) {
                    que.offer(new int[]{r + 1, c});
                    grid[r + 1][c] = 2;
                }
                
                if(c < col - 1 && grid[r][c + 1] == 1) {
                    que.offer(new int[]{r, c + 1});
                    grid[r][c + 1] = 2;
                }
            }
            
            if(que.size() > 0) { // 새로 오염된 오렌지가 존재한다면 시간 증가
                time ++;
            }
        }
        
        for(int[] pos : fresh) { // 모든 fresh 오렌지가 상했는지 검증, 1(= fresh)이 하나라도 있으면 -1 반환
            int i = pos[0];
            int j = pos[1];
            
            if(grid[i][j] == 1) {
                return -1;
            }
        }
        return time;
    }
}