tomato (백준 7576) 🍅 solution 🍅

오늘은 백준 7576번 문제, 토마토를 가져왔습니다
문제 내용은 파악했다고 가정하고 제 사고의 흐름을 바로 설명해볼게요

토마토가 1개라고 가정해볼까요 ?
이 문제는 한 점에서 퍼져나가 모든 토마토을 방문하게 하는 데 ‘최소’ 몇일이 지나야하는지 묻고 있습니다
‘그래프의 최단거리’ 문제와 상당히 유사해보입니다

'그래프 최단거리'라는 어구가 입력 x로 주어지면 저는 반사적으로 'BFS'라는 출력 y를 떠올리는데요
구종만선생님의 책 알고리즘 문제해결전략에서는 DFS와 달리 BFS는 그래프 상에서 ‘최단거리’를 찾는 용도로 제한된다고 했었습니다 이에 반해서 DFS는 그래프의 고유 특징을 추출하는 데 유용해 사용 범위가 넓다고 했죠

아래 코드는 BFS 기본 골격입니다 (예제 소스코드는 c++로 작성되었습니다)

void bfs(int start, const vector<vector<int>>& graph, vector<bool>& visited) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        cout << curr << " "; // 방문한 노드 출력

        for (int next : graph[curr]) {
            if (!visited[next]) {
                q.push(next);
                visited[next] = true;
            }
        }
    }
}

위 코드는 2차원 매트릭스 graph로 인접리스트를 구현하고 있습니다
bfs 구현의 핵심은 자료구조 queue로, 큐를 통해 먼저 투입된 노드를 먼저 방문하고, 이로써 깊이가 얕은 노드들부터 방문할 수 있게 됩니다
또 노드 방문여부를 나타내는 벡터 visited를 통해 노드를 중복해서 방문하지 않게 하고, while 무한루프를 벗어날 수 있게 해줍니다
매 턴마다 큐에서 노드를 꺼내 해당 노드의 인접노드를 큐에 모두 넣은 다음, 인접노드들은 방문한 상태로 처리해주고 있습니다 매 턴마다 방문한 노드는 pop() 해주는 걸 잊지 마세요! (잊으면 무한루프에 빠지게 됩니다…)

토마토 문제의 큰 틀은 우선 이 BFS 소스코드인데, 변수가 있습니다
초기 단계에 익은 토마토가 2개라면 큐에 두 토마토로 인해 익은 토마토들이 들어가야 합니다 그런데 기존 bfs와 달리 같은 날에 익은 토마토(노드)들은 한번에 pop() 해야합니다 문제에서 요구하는 건 모든 토마토가 다 익는데 걸리는 ‘시간’이기 때문이죠 (다른 말로, 시간의 흐름에 따라 익은 토마토들을 구분할 수 있어야 합니다)

제가 생각해낸 방법은 bfs의 큰 틀은 유지하되 2개의 큐를 운용하는 것이었습니다
다음 코드는 응용된 bfs의 큰 틀입니다

while(!q1.empty()) {
    while (!q1.empty()) {
        int curr = q1.front();
        q1.pop();

        for (int next : graph[curr]) {
            if (!visited[next]) {
                q2.push(next);
                visited[next] = true;
            }
        }
    }

    while (!q2.empty()) {
        int curr = q2.front();
        q2.pop();

        for (int next : graph[curr]) {
            if (!visited[next]) {
                q1.push(next);
                visited[next] = true;
            }
        }
    }
}

두 개의 큐는 다음과 같이 운용됩니다
타임라인 상 임의의 시점 t에 대해 현재 시점 t에 방문할 노드는 q1에서 꺼내지고, 다음에 방문해야 할 노드(즉 t+1에 방문될 노드이자 q1에서 꺼내진 노드와 인접한 노드들)들은 q2에 추가됩니다
이 매커니즘은 홀수 시점에 방문할 노드와 짝수 시점에 방문할 노드를 정확히 구분합니다

두 큐를 순회하는 두 while문을 큰 while문이 감싸고 있습니다 이 반복문은 두 큐가 빈 상태인지 확인하는, 즉 탐색이 끝났는지 판단하는 기존 bfs 코드의 while문과 같은 역할을 합니다
이제 while문 사이사이에 시간 t를 업데이트 해주고(t++) 다음과 같은 조건들을 추가해주면 됩니다

• (익은 토마토 수 + 빈자리)의 수가 전체 박스 칸수와 동일한가? -> 첫 순회시 이렇다면 처음부터 익힐 토마토가 없으므로 반복문 탈출 후 -1 출력, 그게 아니라면 탐색을 완료한 것이니 반복문 탈출
• q1 순회 이후에도 여전히 q2가 비어있는가? 혹은 그 반대인가? -> 더 이상 순회할 칸이 없으므로 반복문 탈출

마지막으로 체스판과 같이 특수한 형태로 그래프를 표현하는 코드입니다

int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};

// 가로 M, 세로 N 크기의 매트릭스를 탐색
int nextn, nextm;
for(int i=0;i<4;++i) {
  nextn=nindex+dx[i];
  nextm=mindex+dy[i];
  if(nextn<0 || nextm<0 || nextn>=N || nextm>=M || box[nextn][nextm]==1) continue;
  if(box[nextn][nextm]==0) { q2.push({nextn, nextm}); }
}

체스판, 바둑판은 흔히 2차원 좌표로 나타낼 수 있는데요 말의 이동에 제약이 있다면 (예. 상하좌우로만 이동가능, 대각선 이동불가) 좌표 상에서 증분을 뜻하는 dx,dy 변수를 이용해 보다 쉽게 탐색을 구현할 수 있습니다
이때 취할 수 있는 선택지는 4가지이므로 dx, dy 역시 크기 4의 배열로 표현할 수 있습니다
2차원 벡터로 그래프를 표현하면 인접리스트 또는 인접행렬이 불필요하다는 장점이 있습니다

전체 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
using namespace std;
#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};

int main() {
  fastio;
  queue<pair<int,int>> q1,q2;
  int days=0;
  int rotton=0, non=0;
  int N,M;
  cin >> M >> N;
  int numBox=M*N;
  vector<vector<int>> box(N,vector<int>(M,-1));
  for(int n=0;n<N;++n) {
    for(int m=0;m<M;++m) {
      cin >> box[n][m];
      if(box[n][m]==1) { rotton++; q1.push({n,m}); }
      if(box[n][m]==-1) non++;
    }
  }

  if(rotton+non==numBox) { cout << 0 << '\n'; return 0; }
  while(!q1.empty()) {
    while(!q1.empty()) {
      int nindex=q1.front().first; int mindex=q1.front().second; q1.pop();
      int nextn, nextm;
      for(int i=0;i<4;++i) {
        nextn=nindex+dx[i];
        nextm=mindex+dy[i];
        if(nextn<0 || nextm<0 || nextn>=N || nextm>=M || box[nextn][nextm]==1) continue;
        if(box[nextn][nextm]==0) { box[nextn][nextm]=1; q2.push({nextn, nextm}); rotton++; }
      }
      if(rotton+non==numBox) { cout << days+1 << '\n'; return 0; }
    }
    days++;
    if(q2.empty()) break;
    while(!q2.empty()) {
      int nindex=q2.front().first; int mindex=q2.front().second; q2.pop();
      int nextn, nextm;
      for(int i=0;i<4;++i) {
        nextn=nindex+dx[i];
        nextm=mindex+dy[i];
        if(nextn<0 || nextm<0 || nextn>=N || nextm>=M || box[nextn][nextm]==1) continue;
        if(box[nextn][nextm]==0) { box[nextn][nextm]=1; q1.push({nextn, nextm}); rotton++; }
      }
      if(rotton+non==numBox) { cout << days+1 << '\n'; return 0; }
    }
    days++;
  }
  if(rotton+non != numBox) { cout << -1 << '\n'; return 0; }
  cout << days << '\n';
  return 0;
}