[BOJ] 10711. 모래성

*가장자리는 항상 모래가 있는 부분이기 때문에 1,1 ~ h-1,w-1 의 부분 중 8방향을 살펴봤을 때 '.' 인 부분이 자기 자신보다 많은 경우만 큐에 넣는다. 

즉, 큐에는 이제 사라질 좌표들만 넣는다. 

 

*큐에는 파도에 휩쓸려 사라질 부분들만 넣어지기 때문에 이 부분을 기준으로 

주변에 있는 성들을 탐색하면 된다. 

 

*더 이상 큐에 넣을게 없으면 (= 없어질 게 없으면) 종료 

 

 

#include <iostream> #include <vector> #include <queue> using namespace std; int h, w; char map[1001][1001]; bool visited[1001][1001]; int age[1001][1001]; typedef pair<int, int> pp; typedef pair<pp, int> ppp; int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 }, dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 }; queue<pp> q; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> h >> w; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cin >> map[i][j]; } } for (int i = 1; i < h - 1; i++) { for (int j = 1; j < w - 1; j++) { for (int d = 0; d < 8; d++) { int nx = i + dx[d]; int ny = j + dy[d]; if (map[nx][ny] == '.') { age[i][j]++; } } if (map[i][j] != '.' && age[i][j] >= map[i][j] - '0') { q.push(pp(i, j)); } } } int cnt = 1; while (!q.empty()) { int size = q.size(); while (size--) { int x = q.front().first; int y = q.front().second; q.pop(); for (int i = 0; i < 8; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (map[nx][ny] == '.') continue; age[nx][ny]++; if (map[nx][ny] - '0' == age[nx][ny]) { q.push(pp(nx, ny)); } } } cnt++; } cout << cnt-1 << '\n'; return 0; }