[BOJ] 10711. 모래성

https://www.acmicpc.net/problem/10711

10711번: 모래성

처음에 무너질 모래성을 매번 검사해서 없애주는 방식으로 구현했다가 시간 초과가 났다.

 

 

어차피 나중에 무너질 모래성들은 이전에 무너진 모래성들이 없어져서 영향을 받으므로 무너지는 모래성의 위치로부터

주변을 탐색하여 또 무너질 모래성이 있는지 찾아주고 다시 없애주는 방식으로 구현하면 문제를 해결할 수 있다.

 

 

 

1. 입력을 받는다.
2. 입력 받은 배열에서 튼튼함이 9보다 작은 모든 모래성을 검사하여 자기 격자 주변의 8방향에 모래성이 쌓여있지 않은 부분의 개수가 자기 모래성의 튼튼함보다 많거나 같은 경우 무너질 것이므로 큐에 넣어주고 배열에도 방문 표시를 해준다. 이때 다음에 무너져야 하는 모래성이 영향을 받으므로 바로 ' . '으로 바꿔주면 안 된다.
3. 파도가 한 번 칠 때의 무너질 모래성들을 모두 큐에 넣었다면, ' . '으로 바꿔준다. 그리고 무너질 모래성 주변의 8방향을 다시 검사하여 또 무너질 모래성이 있다면 큐에 넣어준다. 이때 기존에 큐에 들어가 있던 모래성의 개수(큐 사이즈)만큼만 탐색을 진행하여, 탐색이 끝난다면 파도치는 횟수를 증가시킨다.
4. 더 이상 무너질 모래성이 없어서 탐색이 끝난다면 파도치는 횟수를 출력하고 종료한다.

 

#include <iostream>
#include <queue>
using namespace std;
 
int h, w;
char map[1000][1000];
bool visit[1000][1000];
int dx[] = { -1,-1,-1,0,0,1,1,1 };
int dy[] = { -1,0,1,-1,1,-1,0,1 };
 
queue<pair<int, int>> q;
 
int check(int x, int y) {
    int cnt = 0;
    int nx, ny;
 
    //자기 격자 주변의 8방향을 검사하여 모래성이 없다면 cnt증가
    for (int k = 0; k < 8; k++) {
        nx = x + dx[k];
        ny = y + dy[k];
        if (map[nx][ny] == '.') cnt++;
    }
 
    return cnt;
}
 
void solve() {
    queue<pair<int, int> > tmp;
    int time = 0;
 
    int x, y;
 
    //더이상 무너질 모래성이 없을때까지 반복
    while (!q.empty()) {
        tmp = q;
 
        //이전에 무너질 모래성들을 없애준다.
        while (!tmp.empty()) {
            x = tmp.front().first;
            y = tmp.front().second;
            tmp.pop();
            map[x][y] = '.';
        }
 
        int qsize = q.size();
        while (qsize--) {
            x = q.front().first;
            y = q.front().second;
            q.pop();
 
            int nx, ny;
            for (int k = 0; k < 8; k++) {
                nx = x + dx[k];
                ny = y + dy[k];
 
                if (visit[nx][ny]) continue; //이미 체크함
                if (map[nx][ny] == '.') continue; //모래성이 아님
 
 
                //자기 모래성의 튼튼함보다 많거나 같은 경우 파도에 의해서 무너진다.
                if (check(nx, ny) >= (map[nx][ny] - '0')) {
                    q.push(make_pair(nx, ny));
                    visit[nx][ny] = true;
                }
            }
        }
        //시간 증가
        time++;
    }
 
    cout << time << '\n';
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> h >> w;
    for (int i = 0; i < h; i++) cin >> map[i];
 
    int num, cnt;
    //무너질 모래의 위치를 큐에 넣는다.
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (map[i][j] == '.') continue;
 
            num = map[i][j] - '0';
            if (num == 9) continue; //튼튼함이 9이면 무너지지 않으므로 넘어간다
 
            //(i, j)칸 주변 8방향에 모래성이 쌓여있지 않은 부분의 개수
            cnt = check(i, j);
 
            //자기 모래성의 튼튼함보다 많거나 같은 경우 파도에 의해서 무너진다.
            if (cnt >= num) {
                q.push(make_pair(i, j));
                visit[i][j] = true;
            }
        }
    }
 
 
    solve();
 
    return 0;
}