📌 문제 설명

Rotting Oranges 문제 보기

📌 문제 접근

처음에는 BFS로 풀면 되겠구나 생각했는데, 10 * 10 크기길래 그냥 계속 돌리는 식으로 생각했음. 그리고 time이라는 변수를 두어 상한 시간을 재면 되겠구나 생각했었음. 그냥 문제 읽고 바로 푼 문제.

AI의 생각

🚨 팩트 체크 1: 시간 복잡도 vs 공간 복잡도의 트레이드오프 : 매번 풀 스캔 할 경우 시간 초과가 날 위험이 있습니다.

🚨 팩트 체크 2: flat() 사랑 : 코드는 우와하고 예쁘지만, 무거운 작업이므로 투박한 2중 for문으로 하는 것을 추천합니다.

이렇다고 한다. 정석 BFS 대로 좌표를 큐에 담아서 푸는 것이 효율적이라고 한다.

📌 내가 작성한 코드

const orangesRotting = (grid) => {
  const [m, n] = [grid.length, grid[0].length];
  const dx = [0, 0, -1, 1];
  const dy = [-1, 1, 0, 0];
  let time = 2;
  let fresh_oranges = grid.flat(2).filter((e) => e === 1).length;
  while (fresh_oranges > 0) {
    let change_oranges = 0;
    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        if (grid[i][j] === time) {
          for (let l = 0; l < 4; l++) {
            const nx = i + dx[l];
            const ny = j + dy[l];
            if (0 <= nx && 0 <= ny && nx < m && ny < n && grid[nx][ny] === 1) {
              fresh_oranges--;
              change_oranges++;
              grid[nx][ny] = time + 1;
            }
          }
        }
      }
    }

    if (change_oranges === 0) break;
    else time++;
  }
  return grid.flat(2).includes(1) ? -1 : time - 2;
};

📌 시간 복잡도

O(m*n) - 그리드 전체를 최대 한 번씩 순회하며 각 셀의 4방향을 확인하므로

📌 참고 링크

• Array.prototype.flat() - MDN
• BFS 알고리즘 설명