※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 10711번 문제인 모래성이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/10711
다음을 반복하는 것으로 문제의 답을 구해내자.
1) 이전 단계에서 부서진 부분을 참고해 이번 단계에 부서질 부분이 존재하는지를 확인한다. 첫 단계의 경우 예외적으로 직접 부서질 부분을 조사해주자.
1-1) 존재한다면 지금까지 진행된 단계의 수를 하나 증가시킨다.
1-2) 존재하지 않는다면 지금까지 진행된 총 단계수를 출력하고 프로그램을 종료한다.
2) 이번 단계에 부서질 부분을 부순다.
3) 1로 돌아간다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <string>
#include <queue>
#include <vector>
using namespace std;
int R, C;
string board[1000];
bool visited[1000][1000];
queue<pair<int, int>> que;
int dr[8] = { 1,1,1,0,-1,-1,-1,0 };
int dc[8] = { 1,0,-1,-1,-1,0,1,1 };
int ans = 0;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> R >> C;
for (int r = 0; r < R; r++) cin >> board[r];
for (int r = 1; r < R - 1; r++) {
for (int c = 1; c < C - 1; c++) {
if (board[r][c] != '.') {
int cnt = 0;
for (int i = 0; i < 8; i++) {
int rr = r + dr[i], cc = c + dc[i];
if (board[rr][cc] == '.') cnt++;
}
if (cnt >= board[r][c] - '0') visited[r][c] = 1, que.push(make_pair(r, c));
}
}
}
while (!que.empty()) {
ans++;
int quecnt = que.size();
vector<pair<int, int>> vec;
while (quecnt--) {
vec.emplace_back(que.front());
board[que.front().first][que.front().second] = '.';
que.pop();
}
for (auto& p : vec) {
int r = p.first, c = p.second;
for (int k = 0; k < 8; k++) {
int rrr = r + dr[k], ccc = c + dc[k];
if (board[rrr][ccc] == '.' || visited[rrr][ccc]) continue;
int cnt = 0;
for (int i = 0; i < 8; i++) {
int rr = rrr + dr[i], cc = ccc + dc[i];
if (board[rr][cc] == '.') cnt++;
}
if (cnt >= board[rrr][ccc] - '0') visited[rrr][ccc] = 1, que.push(make_pair(rrr, ccc));
}
}
}
cout << ans;
}
728x90
'BOJ' 카테고리의 다른 글
[BOJ 5446 // C++] 용량 부족 (0) | 2023.07.04 |
---|---|
[BOJ 2159 // C++] 케익 배달 (0) | 2023.07.03 |
[BOJ 17136 // C++] 색종이 붙이기 (0) | 2023.07.01 |
[BOJ 5214 // C++] 환승 (0) | 2023.06.30 |
[BOJ 5213 // C++] 과외맨 (0) | 2023.06.29 |