[BOJ] 2636. 치즈

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

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

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

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

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

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

 

 

#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; }