[백준] 7576번 토마토 (C++) - BFS

문제

https://www.acmicpc.net/problem/7576

7576번: 토마토

코드

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int m,n,day=0;
int box[1000][1000];
int isVisited[1000][1000];
queue<pair<int, int>> q;

// 북, 동, 남, 서
int dy[4] = {-1,0,1,0};
int dx[4] = {0,1,0,-1};

bool inRange(int y, int x){
  return (0<=y&&y<n&&0<=x&&x<m);
}

int main(){
  cin >> m >> n;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      cin >> box[i][j];
      isVisited[i][j]=-1;
      if(box[i][j]==1){
        q.push({i,j});
        isVisited[i][j]=0;
      }
    }
  }
  
  while(!q.empty()){
    int y = q.front().first;
    int x = q.front().second;
    q.pop();
    for(int i=0; i<4; i++){
      int ny=y+dy[i];
      int nx=x+dx[i];
      if(inRange(ny, nx)&&isVisited[ny][nx]==-1&&box[ny][nx]==0){
        q.push({ny,nx});
        isVisited[ny][nx]=isVisited[y][x]+1;
      }
    }
  }

  bool flag = true;
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      if(day<isVisited[i][j]){
        day=isVisited[i][j];
      }
      if(box[i][j]==0&&isVisited[i][j]==-1){
        day=-1;
        flag = false;
        break;
      }
    }
    if(!flag) break;
  }

  cout << day;
}

정리

필요한 각각의 원소들을 한 턴마다 처리하려고 할 때 BFS를 사용하면 유용한 것 같다. 이번 문제도 익은 토마토의 위치들을 queue에 모두 저장시키고 한 턴마다 카운트해가면서 풀 수 있는 문제였다.

참조

https://tooo1.tistory.com/166