994. Rotting Oranges

문제

그래프가 주어지고, 값은 0,1,2 중 하나이다. 1은 신선한 토마토, 2는 썩은 토마토, 0은 해당 위치에 토마토가 없음을 표현하였다. 썩은 토마토는 전염시킬 수 있어서, 근접 노드에 신선한 토마토가 있으면 전염시킨다. 전염은 1분 단위로 진행된다. 모든 토마토를 전염시키는데 걸리는 시간을 요구한다. 만약 모든 토마토를 전염시킬 수 없다면 -1를 반환한다.

링크: https://leetcode.com/problems/rotting-oranges/?envType=study-plan-v2&envId=leetcode-75

Solution

class Solution {
    public int orangesRotting(int[][] grid) {
        int[][] visited = grid;
        int m = grid.length;
        int n = grid[0].length;
        int[][] d = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
        int answer= 0;
        Queue<int[]> q = new LinkedList<>();
        int cntFresh = 0;
        for(int i=0; i<m;i++)
            for(int j=0;j<n;j++) {
                if(grid[i][j]==1)
                    cntFresh++;
                if(grid[i][j]==2) {
                    q.offer(new int[]{i,j});
                }
            }

        while(!q.isEmpty()) {
            int curQueueSize = q.size();
            while(curQueueSize > 0) {
                int[] poll = q.poll();
                curQueueSize--;
                for(int i=0;i<4;i++) {
                    int[] next = new int[]{poll[0]+d[i][0], poll[1]+d[i][1]};
                    int r = next[0];
                    int c = next[1];
                    if(r>=0 && r<m && c>=0 && c<n && visited[r][c]==1) {
                        visited[r][c]=2;
                        cntFresh--;
                        q.offer(next);
                    }
                }
            }

            if(q.size()==0)
                break;
            answer++;
        }
        if(cntFresh==0) 
            return answer;

        return -1;
    }
}

전형적인 bfs 문제인 줄 알고, 처음에 그래프의 각 요소를 순차적으로 bfs 탐색하며 문제를 풀었다. 모든 테스트 케이스를 통과하지 못했고, 통과 못한 케이스는 다음과 같다.

 

intput: [[2,1,1], [1,1,1], [0,1,2]]

썩은 토마토는 여러 개 일 수 있고, 전염 진행 과정은 동시에 발생한다는 사실을 간과했다. 여러 노드를 동시에 bfs 탐색해야 하는 문제였다. 동시 탐색을 위해서 우선 썩은 토마토들을 선별해서 큐에 넣었다.

이제부터 큐에 동시에 들어간 노드(순차적으로 들어갔지만 동시간에 전염시킬 썩은 토마토들을 표현하기 위해서 동시로 들어갔다고 표현) 갯수를 기록해야 한다. 큐에 들어 간 노드들은 동시에 전염을 일으킬 썩은 토마토이다. 각 노드가 큐에 빠져나오면서 근접 노드(신선한 토마토)를 전염시킬 것이고, 전염시킨 노드는 큐에 들어갈 것이다. 동시에 넣은 썩은 토마토들이 전부 빠져나올 때마다 1초가 지날 것이다.

하지만 또 간과한 점이 있었다. 근접 신선한 토마토를 전염시킬 때마다 1초가 지나는 것인데, 더 이상 전염시킬 토마토가 없어도 1초가 지나게 됐다. 따라서 큐에 노드가 없으면(더 이상 썩힐 토마토가 없으면) 1초를 증가시키지 않도록 처리했다.

            if(q.size()==0)
                break;
            answer++;

아니면 시작 시간을 0이 아닌 -1로 시작하면 위의 조건문이 필요가 없다. 하지만 나는 -1로 시작 시간을 설정하는 생각을 하지 못했기 때문에 위와 같은 방식으로 접근했다.

회고

bfs 문제에 접근할 때마다 항상 시작점을 하나로 지정하고 노드들을 순회하며 방문 여부를 확인하는 방식으로 풀었었는데, 시간 개념이 적용되면서 잊고 있던 동시에 노드를 탐색하는 문제를 접할 수 있었다.

그리고 큐에 삽입될 노드와 큐에서 빠져나와 처리될 작업 로직을 항상 명확하게 구분하고 신경 써야 한다는 점을 다시 한번 인식하게 되었다.
(ex. 썩은 토마토가 큐에 들어간다. 큐에서 빠져나와 근접 노드가 신선한 토마토인지 탐색하고 신선한 토마토면 큐에 넣고 방문 처리(썩은 토마토 처리)한다.)