baekjoon 2638:치즈

baekjoon 2638 치즈

2638번 치즈

접근

map[0][0]은 무조건 공기가 있는 위치이니 여기서 처음에 bfs를 돌리면 외부 공기 위치를 표시할 수 있다.
공기는 -1, 치즈는 1로 표시했다. 이때 매번 공기랑 2면 이상 접하고 있는 치즈의 위치를 저장해놓고, 각 치즈를 녹인(0으로 만듦)다음
각 치즈의 위치에서 bfs를 돌리면(공기 채우기) 안에 있는 0도 감지할 수 있다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
void search(vector<vector<int>>& map, int dy, int dx, queue<pair<int, int>>& q, pair<int, int> curr);
int countEdge(vector<vector<int>>& map, int y, int x);
int bfs(queue<pair<int, int>>& q, vector<vector<int>>& map, int y, int x);
int main(){
  int n, m; cin >> n >> m;
  vector<vector<int>> map(n, vector<int>(m));
  vector<pair<int, int>> cheeseVector;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> map[i][j];
    }
  }
  //map = 1은 치즈 -1은 공기
  queue<pair<int, int>> q;
  bfs(q, map, 0, 0);//bfs로 공기채우기
  
  int hour = 0;
  while(true){
    //2면 공기 만난 치즈조각 cheeseTemp에 넣음
    vector<pair<int, int>> cheeseTemp;
    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
        // cout << map[i][j] << " ";
        if(map[i][j] == 1){
          int count = countEdge(map, i, j);
          if(count >= 2){
            cheeseTemp.push_back({i, j});
          }
        }
      }
      // cout << endl;
    }
    
    // cout << "---------------\n";
    if(cheeseTemp.size() == 0){
      break;
      //없으면 중단
    }
    for(auto& cheese : cheeseTemp){
      map[cheese.first][cheese.second] = 0;
      //치즈 녹임
    }
    for(auto& cheese : cheeseTemp){
      bfs(q, map, cheese.first, cheese.second);
      //안에 있는 0찾기
    }
    hour++;
  }
  cout << hour;
  
  return 0;
}
void search(vector<vector<int>>& map, int dy, int dx, queue<pair<int, int>>& q, pair<int, int> curr){
  if(curr.first+dy >= 0 && curr.first+dy < map.size() && curr.second+dx >= 0 && curr.second+dx < map[0].size() && (map[curr.first+dy][curr.second+dx] == 0 || map[curr.first+dy][curr.second+dx] == -1)){
    q.push({curr.first+dy, curr.second+dx});
  }
}
int countEdge(vector<vector<int>>& map, int y, int x){
  int count = 0;
  if(y-1 >= 0 && map[y-1][x] == -1){
    count++;
  }
  if(y+1 < map.size() && map[y+1][x] == -1){
    count++;
  }
  if(x-1 >= 0 && map[y][x-1] == -1){
    count++;
  }
  if(x+1 < map[0].size() && map[y][x+1] == -1){
    count++;
  }
  return count;
}
int bfs(queue<pair<int, int>>& q, vector<vector<int>>& map, int y, int x){
  q.push({y, x});
  while(!q.empty()){
    pair<int, int> curr = q.front();
    q.pop();
    if(map[curr.first][curr.second] == 0){
      map[curr.first][curr.second] = -1;
    }
    else if(map[curr.first][curr.second] == -1){
      continue;
    }
    search(map, 1, 0, q, curr);
    search(map, 0, 1, q, curr);
    search(map, -1, 0, q, curr);
    search(map, 0, -1, q, curr);
  }
  return 0;
}

배운 점

bfs응용 해보았다. 상하좌우 bfs코드를 좀더 간결하게 쓸 수 있었던 것 같다.