토마토 백준 7576 c++

문제

토마토 백준 7576

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

int m, n, totalcnt, sweetcnt;
int day = 1e9;
int box[1002][1002];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
queue<pair<pair<int,int>, int>> qu; // {좌표, 일수}

bool checkrange(int i, int j){
  return (i >= 0 && i < n && j >= 0 && j < m);
}

void bfs(){
  while(!qu.empty()){
    int cx = qu.front().X.X;
    int cy = qu.front().X.Y;
    int cday = qu.front().Y;
    qu.pop();
    sweetcnt++;

    day = cday;
    //cout << "sweetcnt:" << sweetcnt << '\n';

    for(int i = 0; i < 4; i++){
      int nx = dx[i] + cx;
      int ny = dy[i] + cy;

      if(!checkrange(nx, ny) || box[nx][ny] != 0) continue;
      box[nx][ny] = 1; // 익히기
      qu.push({{nx, ny}, cday+1});
    }
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> m >> n; // 가로, 세로

  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++) {
      cin >> box[i][j];
      if (box[i][j] != -1) totalcnt++; // 토마토 총 개수 세기
      if (box[i][j] == 1) {
        qu.push({{i, j}, 0}); // 익은 토마토는 시작점
      }
    }
  }

  if(totalcnt == sweetcnt) cout << 0;
  else bfs();

  if(totalcnt == sweetcnt) cout  << day;
  else cout << -1;

  return 0;
}

리뷰

입력 받을 때 총 토마토의 개수를 세 둔다.
토마토가 모두 익지 않았을 때 -1을 출력해야 하기 때문이다.
익은 토마토의 주변에 있는 토마토를 익힐 수 있으니까 처음에 입력받을 때 '익은 토마토의 좌표'를 모두 큐에 넣는다.

 

bfs를 수행할 때, 큐에는 좌표와 날짜를 함께 저장한다. 

좌표의 유효범위를 확인하고, 안익은 토마토가 있으면 익은 것으로 바꾼다.