[BOJ] 2636. 치즈

* 치즈가 없는 좌표(0)에서 탐색할 수 있는 곳에 (상하좌우) 치즈가 있는 좌표(1)가 있다면 -> 이번 타임에 녹는 치즈이다. 

* 큐를 돌고 있는 상황에서 치즈를 바로 없애버리면 (1-> 0) 한 타임에 모든 치즈가 녹아버린다. 

* 위 상황을 방지하기 위해 이번 타임에 녹은 치즈는 map에 -1로 표시한다. 

* 치즈의 개수를 셀 때 -1인 좌표를 0으로 바꾼다. (벡터에 넣어주고 그 좌표들만 0으로 바꿔줘도 되지만, 어차피 치즈 개수 셀 때 모든 맵의 좌표를 탐색하기 때문에 이 때 바꿔주는 것으로 했다.)

* 치즈가 모두 녹아 없을 때까지 (check() == True) 반복한다. 

* 치즈가 모두 녹기 한 시간 전에 있는 치즈의 개수를 세야 하기 때문에 howmanyCheese()를 만들었다. 더 효율적인 방법도 있겠지만, 100*100 이기 때문에 모든 맵을 탐색해도 됐다. 

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

#include <iostream> #include <vector> #include <queue> #include <cstring>   using namespace std;   int n, m; int map[101][101]; bool visited[101][101]; typedef pair<int, int> pp; int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1};   void print() {     cout << '\n';     for (int i = 0; i < n; i++)     {         for (int j = 0; j < m; j++)         {             cout << map[i][j] << ' ';         }         cout << '\n';     }     cout << '\n'; } void bfs(int x, int y) {     memset(visited, 0, sizeof(visited));       queue<pp> q;     q.push(pp(x, y));     visited[x][y] = true;       while(!q.empty()) {         int size = q.size();         while(size--) {             int cx = q.front().first;             int cy = q.front().second;             q.pop();               for (int i = 0; i < 4; i++) {                 int nx = cx + dx[i];                 int ny = cy + dy[i];                   if (nx < 0 || nx >= n || ny < 0 || ny >= m || map[nx][ny] == -1 || visited[nx][ny]) continue;                                   visited[nx][ny] = true;                 if (map[nx][ny] == 1) {                     map[nx][ny] = -1;                 }                 else if (!map[nx][ny]){                     //치즈가 없는 부분만 넣는다.                     q.push(pp(nx, ny));                 }             }         }     } } int howmanyCheese() {     int ret = 0;     for (int i = 0; i < n; i++)     {         for (int j = 0; j < m; j++)         {             if (map[i][j] == -1) map[i][j] = 0;             if (map[i][j] == 1) ret++;         }     }     return ret; } bool check() {     for (int i = 0; i < n; i++)     {         for (int j = 0; j < m; j++)         {             if (map[i][j] == 1) return false;         }     }     return true; } int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       cin >> n >> m;     for (int i = 0; i < n; i++)     {         for (int j = 0; j < m; j++)         {             cin >> map[i][j];         }     }       int time = 0;     int res = 0;     while (1)     {         if (check())             break;           res = howmanyCheese();         bfs(0, 0);         ++time;     }     cout << time << '\n' << res << '\n';     return 0; }