[백준 2636] 치즈

[백준 2636] 치즈

문제 링크

using namespace std;
int n, m, day, cheeze;
int box[101][101];
int check[101][101];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
void input(){
  cin >> n >> m;
  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      cin >> box[i][j];
    }
  }
}
int range(int x, int y) {
  return x >= 0 && y >= 0 && x < n && y < m && !check[x][y];
}
void print() {
  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      cout << box[i][j] << ' ';
    }
    cout << endl;
  }
  
}
int melt() {
  queue <pair<int, int>> q;
  memset(check, 0, sizeof(check));
  q.push({0, 0});
  check[0][0] = 1;

  // 외곽선 체크
  while (!q.empty()){
    int top_x = q.front().first;
    int top_y = q.front().second;
    q.pop();

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

      if(!range(nx, ny) || box[nx][ny]) continue;

      check[nx][ny] = 1;
      q.push({nx, ny});
    }
  }

  int cnt = 0;
  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      if(box[i][j]) {
        cnt++;
        for(int k=0; k<4; k++) {
          int nx = i + dx[k];
          int ny = j + dy[k]; //상하좌우 탐색
          if(check[nx][ny]) { // 외곽선 인접이라면
            box[i][j] = 0;
            break;
          }
        }
      }
    }
  }

  if(cnt == 0) return true;
  else {
    cheeze = cnt;
    return false;
  }
}
void solve(){

  while(true) {
    if(melt()) break;
    day++;
  }

  cout << day << endl << cheeze << endl;

}
int main() {
  input();
  solve();
  return 0;
}

• 전형적인 bfs 문제
• bfs를 0, 0 부터 돌면서 외곽선을 체크 해 준다.
• 다시 한 번 bfs를 돌면서 주변에 외곽선이 있는 경우에만 녹여준다.