[LeetCode] 994. Rotting Oranges - 문제풀이

Description

주어진 매트릭스에서 썩은오렌지(2)가 주위 4방향의 오렌지(1)을 1초에 한칸씩 썩게 만드는데 이때 전체 오렌지를 썩게 만드는데 걸리는 시간을 구하는 문제입니다.

You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,
• 1 representing a fresh orange, or
• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2.

Solution 1. BFS(Breadth-First Search) - level체크

public int orangesRotting(int[][] grid) {

    int m = grid.length;
    int n = grid[0].length;

    Queue<int[]> q = new LinkedList<>();
    int freshCnt = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            int curr = grid[r][c];
            switch (curr) {
                case 1: freshCnt++; break;
                case 2: q.offer(new int[]{r, c});  break;  // offer rottenOrange in queue
            }
        }
    }
    if(freshCnt == 0){return 0;} // edge case

    // start rot
    int level = 0;
    while(!q.isEmpty()){
        int qSize = q.size();
        for(int i = 0 ; i < qSize ; i++) {
            int[] curr = q.poll();
            for (int[] d : DIRECTIONS) {
                int nr = curr[0] + d[0];
                int nc = curr[1] + d[1];
                if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] != 1) {
                    continue;
                } else {
                    grid[nr][nc] = 2; // be rotten
                    freshCnt--; // 전부 다 채워졌는지 확인하기 위함
                    q.offer(new int[]{nr, nc});
                }
            }
        }
        level++;
    }
    //남은 오렌지가 있는 경우 -1
    return freshCnt > 0? -1 : level-1;
}

너비 우선 검색(BFS)를 이용한 방법입니다. 먼저 순회하면서 freshOrange(1) 개수를 기록하고 탐색 시작점인 rottenOrange(2)를 모두 큐에 넣어 줍니다.

더 이상 썩게 할 freshOrange가 없을 경우 진행할 것 없이 바로 0초를 반환해 주고 이후 BFS 알고리즘을 이용해 1초마다 freshOrange(1)를 rottenOrange(2)로 바꿔주며 freshCnt 를 줄여나갑니다.

이후 freshCnt가 남아있다면 진행 불가능한 케이스니 -1를 반환하고 아니라면 BFS를 진행한 level을 반환해주면 됩니다.

Solution 2. BFS(Breadth-First Search) - 거리 기록

public int orangesRotting(int[][] grid) {

		int m = grid.length;
	  int n = grid[0].length;
	
	  Queue<int[]> q = new LinkedList<>();
	  int freshCnt = 0;
	  for (int r = 0; r < m; r++) {
	      for (int c = 0; c < n; c++) {
	          int curr = grid[r][c];
	          switch (curr) {
	              case 1: freshCnt++; break;
	              case 2:
	                  q.offer(new int[]{r, c});  // offer rottenOrange in queue
	                  break;
	          }
	      }
	  }
	
	  if(freshCnt == 0){return 0;} // edge case
	
	  // start rot
	  int minute = 0;
	  while(!q.isEmpty()){
	      int[] curr = q.poll();
	      for(int[] d: DIRECTIONS){
	          int nr = curr[0] + d[0];
	          int nc = curr[1] + d[1];
	          if(nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] != 1) {
	              continue;
	          }else{
	              grid[nr][nc] = grid[curr[0]][curr[1]]+1; // +1 minute (거리 = 1분)
	              minute = Math.max(minute,grid[nr][nc]);  // 최대값이 전부다 rotten 채워지는 시간
	              freshCnt--; // 전부 다 채워졌는지 확인하기 위함
	              q.offer(new int[]{nr,nc});
	          }
	      }
	  }
	
	  //남은 오렌지가 있는 경우 전부 다 안 채워진 고립케이스 & 2부터의 거리가 만들어지기 때문에 -2
	  return freshCnt > 0? -1 : minute-2;
}

1번과 거의 유사한 접근이나 BFS의 level이 아니고 rottenOrange인 2부터 시작하는 거리를 매트릭스에 기록한뒤 가장 큰 거리에서 시작점(2)를 제외하고 반환하면 동일한 결과를 얻을 수 있습니다. 원본 매트릭스의 freashOrange가 2가 아닌 3부터 시작하는 거리로 변경되어 있다는 차이점이 있습니다.

Reference

Rotting Oranges - LeetCode