/* 모눈종이 얇은 ㄴ치즈. 엔은 세로 격자의 수 , 엠은 가로 격자의 치즈는 냉동 보관 실내온도에 공기 접 4변 중에 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹습니다. 따라서 아래모양 치즈라면 시로 치즈 격자는 한시간 후에 사라짐. 오께이 그럼 삭제할때 조건이 맵은 1이고 주변 동서남북을 돌렸을때 0,1,2,3 중에 2개 이상이 0이면 삭제되도록 erase 하는 부분만 다시 해주면 됩니다. 오께이 그럼 다시 작성해보도록 하겟습니다. 체크가 1이면 이제 그 x,y 맵에서 x,y 주변에 동서남북 돌렸을 때 0이 2개 이상이면 지우면 됩니다. */ #include <iostream> #include <queue> #define SIZE 10 using namespace std; int map[SIZE][SIZE]; int check[SIZE][SIZE]; int n, m, x, y, nx, ny; struct points{ int x,y; }; queue<points> que; int hour; int chz_num; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; int sur_zero_cnt; void problemIn() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; check[i][j] = 1; } } } void find_zero() { que.push({ 0,0 }); check[0][0] = 0; while (!que.empty()) { x = que.front().x; y = que.front().y; que.pop(); for (int i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < n && ny < m) { if (map[nx][ny] == 0 && check[nx][ny] == 1) { check[nx][ny] = 0; que.push({ nx,ny }); } } } } } void erase() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (check[i][j] == 1) { sur_zero_cnt = 0; for (int k = 0; k < 4; k++) { nx = i + dx[k]; ny = j + dy[k]; if (check[nx][ny] == 0) { sur_zero_cnt++; } if (sur_zero_cnt == 2) { map[i][j] = 0; } } } } } } void check_chz_num() { chz_num = 0; for(int i=0; i<n; i++) for (int j = 0; j < m; j++) { if (map[i][j] == 1) { chz_num++; } } } void check_init() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { check[i][j] = 1; } } } void solve() {
check_chz_num(); while (chz_num > 0) { find_zero(); erase(); check_init(); check_chz_num(); hour++; } } int main(void) { problemIn(); solve(); cout << hour << endl; return 0; }
|
맵과 체크 2차원 어레이를 받습니다. 바로바로 결과가 적용되지 않도록 주의하는 것이 필요한 부분이 있습니다. 이를 잘 알고 디버깅하면서 체크하도록 합니다. 베이프에스에 대해서는 어느정도 익숙하게 되었습니다. dfs 의 기본 문제에 대해서 풀어보도록 하겠습니다. |