[BOJ] 백준 2638 치즈

[BOJ] 백준 2638 치즈

문제 링크 : https://www.acmicpc.net/problem/2638

이 문제 또한 마찬가지(2636 치즈) 마찬가지 유형이다.

다른점이라고는, 2636번에선 치즈가 외부공기와 닿기만해도 썩어버렸는데, 이번엔 두번 닿아야 썩는 것이다. 그래서 hp개념을 도입했다. hp가 2가 되면 썩는 것이다. 알고리즘은 동일하나, if-else 부분을 추가해서 hp를 늘렸다.

소스코드 :

#include 
#include 
#include 
using namespace std;


int a, b;
vector< vector > v(101, vector(101, 0));
vector< vector > visited(101, vector(101, 0));
vector< vector > hp(101, vector(101, 0));

// 4방향 탐색 방향 지정
struct dir{
 int x, y;
};
dir Dir[4] = { {-1,0}, {1,0}, {0,-1}, {0,1} };

// 외부공기를 탐색할 DFS
void dfs(int x, int y) {
 for (int i = 0; i < 4; i++) {
  int rx = x + Dir[i].x;
  int ry = y + Dir[i].y;
  if (rx >= 0 && rx < a && ry < b && ry >= 0)
  {
   if (v[rx][ry] != 1 && visited[rx][ry] == 0) {
    v[rx][ry] = -1;
    visited[rx][ry] = 1;
    dfs(rx,ry);
   }
  }
 }
}


int main() {
 cin >> a >> b;
 cin.ignore();
 int cnt = 0; 
 for (int i = 0; i < a; i++) {
  for (int j = 0; j < b; j++) {
   cin >> v[i][j];
   if (v[i][j] == 1) {
    cnt++;    // 1의 개수를 센다.
   }
  }
  cin.ignore();
 }
 int timer = 0;
 // 초기 외부공기 탐색
 dfs(0, 0);

 while (cnt > 0) {
  // 시간을 탐지할 timer
  timer++;
  vector> pairvec;
  for (int i = 1; i < a-1 ; i++) {
   for (int j = 1; j < b-1 ; j++) {
    if (v[i][j] == 1) {
     if (v[i - 1][j] == -1)
      hp[i][j]++;
     if (v[i + 1][j] == -1)
      hp[i][j]++;
     if (v[i][j - 1] == -1)
      hp[i][j]++;
     if (v[i][j + 1] == -1)
      hp[i][j]++;
      // 없애야 할 치즈를 벡터에 넣음.
     if(hp[i][j] >=2)
      pairvec.push_back({ i,j }); 
     }
    }
   }
  // 치즈 썩은거 없앰 (그리고 -1로 초기화(외부공기니까))
  for (int w = 0; w < pairvec.size(); w++) {
   v[pairvec[w].first][pairvec[w].second] = -1;
   cnt--; 
  }
  // 다시 외부공기 탐색.
  for (int i = 0; i < a; i++) {
   for (int j = 0; j < b; j++) {
    hp[i][j] = 0;
    if (visited[i][j] != 1 && v[i][j] == -1) {
     dfs(i, j);
    }
   }
  }
 }
 cout << timer << endl ;
}