백준 2638번 치즈[C++]

1. 문제 풀이

외부 공기와 내부 공기를 구분하는 것이 이 문제의 핵심인데요. 모눈종이 가장자리에 치즈가 놓이지 않는다고 하였으니 너비 우선 탐색으로 외부 공기를 -1로 값을 변경한 뒤, 치즈가 모두 녹을 때까지 외부 공기에 접촉한 가장자리 치즈를 찾아서 지워주시면 됩니다. 여기서 치즈가 녹으면서 외부공기가 접촉한 내부 공기가 있다면 너비 우선 탐색으로 flood fill 하면서 -1로 만들어주었습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int n, m;
int board[105][105];
vector<pi> edge;

/*
  외부 공기를 모두 -1로 값을 바꾼다.
*/
void fill_air(int x, int y){
  qpi q;
  board[x][y] = -1;
  q.push({x, y});
  while(sz(q)){
    auto [cx, cy] = q.front(); q.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cx + dx[dir];
      int ny = cy + dy[dir];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if(board[nx][ny] != 0) continue;
      board[nx][ny] = -1;
      q.push({nx, ny});
    }
  }
}

bool chk(int x, int y){
  int cnt{};
  for(int dir = 0; dir < 4; dir++){
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    cnt += (board[nx][ny] == -1);
  }
  return cnt >= 2;
}

void edge_detect(){
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(board[i][j] == 1 && chk(i, j)) edge.pb({i, j});
    }
  }
}


int main() {
  fastio(nullptr, false);

  // input
  int cheese{};
  cin >> n >> m;
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> board[i][j];
      if(board[i][j]) cheese++;
    }
  }

  // init
  fill_air(0, 0);

  // solve
  int ans{};
  // cheese의 개수가 0이 아니라면
  while(cheese){
    // 가장 자리에 놓인 치즈를 탐지한다.
    edge_detect();

    cheese -= sz(edge);

    while(sz(edge)){
      auto cur = edge.back(); edge.pop_back();
      board[cur.X][cur.Y] = -1;
      for(int dir = 0; dir < 4; dir++){
        int nx = cur.X + dx[dir];
        int ny = cur.Y + dy[dir];
        if(board[nx][ny] == 0) fill_air(nx, ny);
      }
    }

    ans++;
  }

  cout << ans;
}

 

3. 코드

처음에 외부가 아니라 내부에 초점을 맞추어서 값을 변경해보려고 하다고 시간을 다 버렸습니다.