[BOJ] 백준 2636 치즈

[BOJ] 백준 2636 치즈

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

이 문제에서 맨처음에 생각할 때 외곽 라인을 어떻게 그리지? 에서 막혔었다.

그래서 다각형의 외곽 선을 어떻게 판별하는지 구글 검색하고 했었다.

그런데 도통 모르겠어서 인터넷 검색했더니, 그냥 외곽선 바깥에서부터 DFS/BFS 하면 되는 문제였다. 접근방법은 이렇다.

시간이 흐를수록 외부공기에 있는 치즈는 썩는다. 이 문제의 관건은 외부공기와 내부공기를 구분하는건데, DFS는 외부공기만 하면서 0이나 1이 아닌 -1로 색칠을 해주면 되는 문제다.

그래서 치즈입장에서는 -1인 공기와 접촉했을경우에만 썩으니까.

소스코드 : 

#include 
#include 
#include 
using namespace std;


int a, b;
vector< vector > v(101, vector(101, 0));
vector< vector > visited(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 cheesCnt ;
 int timer = 0;
 // 초기 외부공기 탐색
 dfs(0, 0);

 while (cnt > 0) {
  // 시간을 탐지할 timer
  timer++;
  // 이전까지 몇개의 치즈가 있었는지 저장할 변수
  cheesCnt = 0;
  vector> pairvec;
  for (int i = 1; i < a-1 ; i++) {
   for (int j = 1; j < b-1 ; j++) {
    if (v[i][j] == 1) {
     cheesCnt++;
     if (v[i - 1][j] == -1 || v[i + 1][j] == -1 || v[i][j - 1] == -1 || v[i][j + 1] == -1) {
      // 없애야 할 치즈를 벡터에 넣음.
      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++) {
    if (visited[i][j] != 1 && v[i][j] == -1) {
     dfs(i, j);
    }
   }
  }
 }
 cout << timer << endl << cheesCnt << endl;
 
}