※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 10711번 문제인 모래성이다.
문제는 아래 링크를 확인하자.

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

 

10711번: 모래성

첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이

www.acmicpc.net

다음을 반복하는 것으로 문제의 답을 구해내자.

 

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

+ Recent posts