백준 10711번 [모래성](C++) -yes6686- 티스토리

백준 문제 풀이: 10711 (모래성)

---

문제 링크: https://www.acmicpc.net/problem/10711

문제 설명:

모래사장의 모래성은 1부터 9까지의 강도를 가지며, 주변 8방향에 있는 파도가 침식되면 해당 강도만큼 버틸 수 있습니다. 빈 칸(.)은 이미 파도가 찬 상태이며, 매 시간마다 강도 이하로 주변 파도가 몰아치면 해당 성은 무너져 파도가 됩니다. 몇 초가 지나면 더 이상 무너질 모래성이 없는지 계산하는 시뮬레이션 문제입니다.

이 문제는 BFS 또는 큐를 이용한 시뮬레이션으로 해결할 수 있으며, 각 턴마다 무너질 성을 계산하고 다음 턴에 영향을 줄 성들을 반복적으로 갱신합니다.

---

문제 해결 코드

// 모래성 (BFS 방식 시뮬레이션)
#include <iostream>
#include <queue>
using namespace std;

char arr[1001][1001];               // 모래성 보드
int visited[1001][1001];           // 방문 체크
int dx[8] = { -1,-1,-1, 0, 0, 1, 1, 1 };
int dy[8] = { -1, 0, 1,-1, 1,-1, 0, 1 };

queue<pair<int, int>> q1, q2;        // 붕괴될 모래성, 영향을 받을 모래성
vector<pair<int, int>> v;          // 다음 라운드에서 검사할 모래성 후보

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int h, w;
    cin >> h >> w;

    for (int i = 0; i < h; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); j++) {
            arr[i][j] = s[j];
            if (arr[i][j] != '.') {
                v.push_back({ i, j });  // 모래성이 있는 위치 저장
            }
        }
    }

    int ans = 0;

    while (true) {
        // 이번 라운드에 무너질 모래성 탐색
        for (auto [x, y] : v) {
            int sea = 0;
            for (int d = 0; d < 8; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                if (arr[nx][ny] == '.') sea++;
            }
            if (arr[x][y] - '0' <= sea) {
                q1.push({ x, y });
                visited[x][y] = 1;
            }
        }

        v.clear();
        bool changed = false;

        // 실제 붕괴 수행
        while (!q1.empty()) {
            auto [x, y] = q1.front(); q1.pop();
            arr[x][y] = '.';  // 무너짐
            for (int d = 0; d < 8; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                if (visited[nx][ny]) continue;

                if (arr[nx][ny] >= '1' && arr[nx][ny] <= '9') {
                    visited[nx][ny] = 1;
                    q2.push({ nx, ny });
                }
            }
            changed = true;
        }

        // 다음 라운드 후보 갱신
        while (!q2.empty()) {
            auto [x, y] = q2.front(); q2.pop();
            visited[x][y] = 0;
            v.push_back({ x, y });
        }

        if (!changed) break;
        ans++;
    }

    cout << ans << '\n';
}

---

코드 설명

• 핵심 알고리즘: 시뮬레이션 + 큐 활용. 매 시간마다 붕괴될 모래성을 찾아 큐에 넣고, 붕괴 후 주변에 영향을 미칠 수 있는 모래성을 다음 라운드 후보로 저장합니다.
• 구현 세부사항: q1은 이번 라운드에 무너질 모래성, q2는 다음에 검사할 모래성 후보입니다. visited 배열로 중복 체크합니다.
• 시간 복잡도 분석: O(h ⋅ w), 모든 셀을 한 번씩만 붕괴 처리하므로 효율적입니다.

---

결과

시뮬레이션이 종료되기까지 걸리는 시간(턴)을 출력합니다.

예시 입력:

5 5
.....
.324.
.999.
.324.
.....

예시 출력:

1

다른 접근 방식이나 개선 아이디어가 있다면 댓글로 공유 부탁드립니다!