백준(BOJ) 2638 : 치즈

https://www.acmicpc.net/problem/2638

2638번: 치즈

 

 

https://www.acmicpc.net/problem/2636

2636번: 치즈

매우매우 비슷한 문제

차이가 있다면 치즈가 녹을 조건이 공기와 맞닿은 칸이 2칸 이상이여야 한다는 것이다.

 

치즈로 둘러쌓인 내부는 공기가 침투할수없으므로 맨 바깥에서 부터 bfs를 돌려주자.

모눈종이의 모서리부분은 치즈가 존재할 수 없다고 문제에 명시되어있으므로 왼쪽 위에서 부터 bfs를 돌려준다.

공기에 도착할 경우 방문한 지점이라는 걸 확인해주고 치즈에 도착한 경우에는 더 진행할 필요가 없으므로 패스한다.

단 여기서 공기와 맞닿은 칸이 두 개 이상인지 확인하기 위해서 치즈에 도착한 경우에는 배열의 값을 1 증가시켜주었다.

따라서 공기가아니고 배열의 값이 3 이상인 경우에는 두 번 이상 공기와 맞닿았으므로 녹을 것이다. 아닐 경우 1로 다시 배열의 값을 되돌려주자. 모든 배열의 값이 0이 될때까지 bfs를 몇 번 돌려야하는지 세주면 된다~

아래는 소스코드이다.

 

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define cont continue  
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 2147483646;
const double pi = 3.141592653589793;

int N, M;
int board[101][101] = {};
int ch = 0;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
bool visit[101][101] = {};

bool isRange(int y, int x) {
  if(y < 0 || y > N || x < 0 || x > M) return false;
  else return true;
}

bool foo() {
  for(int i = 1 ; i <= N ; i++) {
    for(int j = 1 ; j <= M ; j++) {
      if(board[i][j] != 0) {
        return false;
      }
    }
  }
  return true;
}

void bfs() {
  queue<pii> q;
  q.push(mp(0, 0));
  visit[0][0] = true;
  while(!q.empty()) {
    int cy = q.front().first;
    int cx = q.front().second;
    q.pop();
    if(board[cy][cx] != 0) {
      board[cy][cx]++;
      continue;
    }
    for(int i = 0 ; i < 4 ; i++) {
      int ny = cy + dy[i];
      int nx = cx + dx[i];
      if(!isRange(ny, nx)) continue;

      if(!visit[ny][nx]) {
        if(board[ny][nx] == 0) visit[ny][nx] = true;
        q.push(mp(ny, nx));
      }
    }
  }
  for(int i = 1 ; i <= N ; i++) {
    for(int j = 1 ; j <= M ; j++) {
      if(board[i][j] >= 3) {
        board[i][j] = 0;
      }
      else if(board[i][j] != 0) {
        board[i][j] = 1;
      }
    }
  }
  return;
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin >> N >> M;

  for(int i = 1 ; i <= N ; i++) {
    for(int j = 1 ; j <= M ; j++) {
      cin >> board[i][j];
    }
  }
  int tc = 0;
  while(1) {
    if(foo()) {
      cout << tc << endl;
      return 0; 
    }
    memset(visit, false, sizeof(visit));
    bfs();
    tc++;
  }
}