baekjoon 7576:토마토 (bfs level 나누기)

baekjoon 7576 토마토

7576번 토마토

접근

보자마자 딱 bfs 생각이 났다. level나눠서 했던 bfs가 생각나면서
같은 level에 각각 거리 1씩 더 탐색하는 방식이 떠올랐다.
초기에 익은 토마토가 여러개라면 그 토마토들과 모두 연결되어 있는
부모 토마토(node)가 있다 생각하면 완벽히 bfs 모양이다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int nearbfs(vector<vector<int>>& graph, pair<int, int> curr, queue<pair<int, int>>& q);
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int m, n;
  cin >> m >> n;
  vector<vector<int>> graph(n, vector<int>(m));
  queue<pair<int, int>> q;
  int count = 0; //토마토 총 개수 세기
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      int temp;
      cin >> temp;
      graph[i][j] = temp;
      if(temp >= 0){
        count++;
        if (temp == 1){
          q.push({i, j});
        }
      }
    }
  }
  int result = q.size();  //처음있는 익은 토마토 수
  int level = 0;
  while(!q.empty() && result < count){ //result < count 넣은건 마지막에 다 익었는데도 안익은거 탐색하지 말라고
    int qsize = q.size();
    for(int i = 0; i < qsize; i++){ //qsize만큼만 돌리면 딱 같은 level node pop 끝날 때 까지만 돈다
      pair<int, int> curr = q.front();
      q.pop();
      result += nearbfs(graph, curr, q);
    }
    level++;
    // cout << result << "\n";
    // for(int i = 0; i < n; i++){
    //   for(int j = 0; j < m; j++){
    //     cout << graph[i][j];
    //   }
    //   cout << "\n";
    // }
    // cout << "--------------\n";
  }
  if(result < count){
    cout << -1;
  }
  else if (result == count){ //다 익었는지 확인
    cout << level;
  }
  
  
  
  
  return 0;
}
int nearbfs(vector<vector<int>>& graph, pair<int, int> curr, queue<pair<int, int>>& q){
  int changeCount = 0;
  if(curr.first - 1 >= 0 && graph[curr.first - 1][curr.second] == 0){ //graph[][] == 0으로 visited 판별
    q.push({curr.first - 1, curr.second});
    graph[curr.first - 1][curr.second] = 1;
    changeCount++;
  }
  if(curr.first + 1 < graph.size() && graph[curr.first + 1][curr.second] == 0){
    q.push({curr.first + 1, curr.second});
    graph[curr.first + 1][curr.second] = 1;
    changeCount++;
  }
  if(curr.second - 1 >= 0 && graph[curr.first][curr.second - 1] == 0){
    q.push({curr.first, curr.second - 1});
    graph[curr.first][curr.second - 1] = 1;
    changeCount++;
  }
  if(curr.second + 1 < graph[0].size() && graph[curr.first][curr.second + 1] == 0){
    q.push({curr.first, curr.second + 1});
    graph[curr.first][curr.second + 1] = 1;
    changeCount++;
  }
  return changeCount; //안익은거가 익게 된 개수
}

배운 점

bfs에서 level나누는 방법 구현해보았다.