[백준 5212] 지구 온난화

[백준 5212] 지구 온난화

문제 링크

#include "header.h"
using namespace std;
int R, C;
char ocean[14][14];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
queue <pair<int, int>> q;
vector <pair<int, int>> v;
bool cmp(pair<int, int>&a, pair<int, int>&b) {
  return a.second < b.second;
}
void input() {
  cin >> R >> C;

  for(int i=0; i<R; i++) {
    for(int j=0; j<C; j++) {
      cin >> ocean[i][j];
      if(ocean[i][j] == 'X') {
        q.push({i, j});
      }
    }
  }
}
void solve() {
  vector <pair<int, int>> del;
  while (!q.empty()){
    int top_x = q.front().first;
    int top_y = q.front().second;
    q.pop();

    int cnt = 0;
    for(int i=0; i<4; i++) {
      int nx = top_x + dx[i];
      int ny = top_y + dy[i];
      if(ocean[nx][ny] == 'X') continue;
      if(nx < 0 || ny < 0 || nx >= R || ny >= C) {
        cnt++; continue;
      }
      else cnt++;
    }

    if(cnt >= 3) del.push_back({top_x, top_y});
    else v.push_back({top_x, top_y});
  }

  for(int i=0; i<del.size(); i++) ocean[del[i].first][del[i].second] = '.';

  print();
}
void print() {
  sort(v.begin(), v.end());
  int i_begin = v.front().first;
  int i_end = v.back().first;

  sort(v.begin(), v.end(), cmp);
  int j_begin = v.front().second;
  int j_end = v.back().second;

  for(int i=i_begin; i<=i_end; i++) {
    for(int j=j_begin; j<=j_end; j++) {
      cout << ocean[i][j];
    }
    cout << endl;
  }
}
int main() {

  input();
  solve();

  return 0;
}

• bfs 돌면서 4면을 탐색한다.
• cnt가 3 이상이면 바다가 될 곳이므로 del에 저장 해 준다. 이때 바로 삭제 하게 되면 다른 섬에도 영향을 끼치게 되므로 일단 벡터에 따로 저장 해 놓는다.
• 바다가 되지 않을 곳들도 따로 벡터에 저장 해 놓는다.
• del 벡터를 돌면서 바다로 바꿔준다.
• 벡터를 정렬 해 범위를 찾는다. 이후 출력.