Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 썩어가는 오렌지(Rotting Oranges) 문제 완벽 정리

문제 개요

격자(grid) 형태의 2차원 배열이 주어지며, 각 칸은 아래 세 가지 값 중 하나를 가집니다.

  • 0 : 빈 칸
  • 1 : 신선한 오렌지
  • 2 : 썩은 오렌지

매 분마다 썩은 오렌지와 상하좌우로 인접해 있는 신선한 오렌지는 함께 썩게 됩니다. 우리가 구해야 할 것은 모든 오렌지가 썩을 때까지 걸리는 최소 시간(분)입니다. 만약 어떤 신선한 오렌지가 끝까지 썩을 수 없는 상황이라면 -1을 반환해야 합니다.

예를 들어 입력이 [[2,1,1],[1,1,0],[0,1,1]]과 같다면, 결과값은 4가 됩니다.

C++로 풀어보는 썩어가는 오렌지(Rotting Oranges) 문제 완벽 정리

해결 접근 방법

이 문제는 매 단계마다 격자 전체를 확인하면서, 썩은 오렌지 옆에 있는 신선한 오렌지를 찾아 썩히는 방식으로 해결할 수 있습니다. 핵심 로직은 다음과 같습니다.

  • minutes : 경과 시간(분)을 저장하는 변수, 초기값 0
  • rowMax, colMax : 격자의 행과 열 크기
  • freshLeft : 아직 남아 있는 신선한 오렌지가 있는지 여부
  • newGrid : 현재 상태를 복사한 임시 격자

반복문 안에서는 다음 과정을 수행합니다.

  1. 현재 격자를 newGrid에 복사하고, 변경 여부를 나타내는 flag와 freshLeft를 초기화합니다.
  2. 모든 칸을 순회하면서 값이 1(신선한 오렌지)인 칸을 찾습니다.
  3. 해당 칸의 상하좌우 중 하나라도 2(썩은 오렌지)가 있다면, 그 칸을 2로 바꾸고 flag를 true로 설정합니다.
  4. 신선한 오렌지가 하나라도 발견되면 freshLeft를 true로 유지합니다.
  5. 이번 반복에서 변경된 칸이 있었다면(flag가 true) minutes를 1 증가시키고, 그렇지 않으면 반복을 종료합니다.

마지막으로 freshLeft가 false라면 모든 오렌지가 썩은 것이므로 minutes를 반환하고, true라면 썩을 수 없는 오렌지가 남아 있는 것이므로 -1을 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작을 확인해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int orangesRotting(vector<vector<int>> &grid) {
      int minutes = 0;
      int rowMax = grid.size();
      int colMax = grid[0].size();
      bool freshLeft = false;
      auto newGrid = grid;
      while (true) {
         newGrid = grid;
         bool flag = false;
         freshLeft = false;
         for (int i = 0; i < rowMax; i++) {
            for (int j = 0; j < colMax; j++) {
               if (newGrid[i][j] == 1) {
                  if ((i - 1 >= 0 && newGrid[i - 1][j] == 2) || (i + 1 < rowMax && newGrid[i + 1][j] == 2) || (j - 1 >= 0 && newGrid[i][j - 1] == 2) || (j + 1 < colMax && newGrid[i][j + 1] == 2)) {
                     grid[i][j] = 2;
                     flag = true;
                  }
                  freshLeft = true;
               }
            }
         }
         if (flag)
            minutes++;
         else
            break;
      }
      return (freshLeft != true) ? minutes : -1;
   }
};
main() {
   Solution ob;
   vector<vector<int>> v = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};
   cout << (ob.orangesRotting(v));
}

입력

{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}

출력

4

추가 팁: BFS를 활용한 최적화

위 방법은 직관적이지만, 매 분마다 격자 전체를 다시 탐색하기 때문에 시간 복잡도가 O(N×M×T)로 비효율적일 수 있습니다. 실전에서는 BFS(너비 우선 탐색)를 활용하는 것이 좋습니다. 처음부터 모든 썩은 오렌지를 큐에 넣고, 레벨 단위로 인접한 신선한 오렌지를 동시에 썩혀 나가면 O(N×M)의 시간 복잡도로 문제를 해결할 수 있습니다. 이는 LeetCode의 'Rotting Oranges' 문제에서 권장되는 표준 풀이 방식이기도 합니다.