백준 10711 모래성 C++ 풀이 - BFS

모래성 문제.
모래성에 파도가 치는데, 모래성이 감당할 수 있는 것보다 큰 파도를 만나면 모래성이 무너진다.
얼마나 많은 시간이 지나야 모래성의 모습이 더이상 변하지 않을까?

우선 특수한 경우가 어떤 것이지부터 파악했다.
1. 가장자리에는 모래성이 없다.
2. 튼튼함이 9인 경우 반드시 무너지지 않는다.
3. 맵의 크기가 백만이므로 완전탐색으로 풀 수 없다.

이 세 가지를 이용해 코드의 방향과
최적화를 잡을 수 있을 것으로 기대한다.

우선 가장 빨리 결과에 도착하는 시간을
찾는 것이기 때문에 BFS 를 생각했다.
맵의 크기가 너무 크기도 해서
DFS 로는 시간 초과가 뜰 것이 분명했기 때문이다.

풀이 방식은 다음과 같다.
1. 초기 상태에서 무너질 수 있는 곳의 좌표를 찾아서 저장한다.
2. 무너질 수 있는 곳의 값을 파도('.')로 바꾼다.
3. 새롭게 생긴 파도 주위로 무너질 수 있는 모래성을 찾아서 좌표를 저장한다.
4. 2~3 반복. 더 이상 무너질 수 있는 곳이 없다면 종료한다.

#include <iostream>
#include <queue>
using namespace std;
#define MAX 1001
int H, W;
char Castle[MAX][MAX];

//파도가 친 횟수, y, x
queue<pair<int,pair<int, int>>> q;

//8방향
int dy[8] = { -1,-1,-1,0,1,1,1,0 };
int dx[8] = { -1,0,1,1,1,0,-1,-1 };




int timelapse() {
//초기에 무너질 수 있는 곳 찾기
//파도가 있는 곳과 '9'를 제외한 곳의
//튼튼함 - 주변의 파도 수를 해주고 그 값이 0보다 작은 곳이 초기에 무너질 수 있는 곳이므로 저장.
	for (int y = 0; y < H ; y++) {
		for (int x = 0; x < W ; x++) {
			if (Castle[y][x] == '.') {
				for (int i = 0; i < 8; i++) {
					int ny = y + dy[i];
					int nx = x + dx[i];
					if (ny >= H || ny < 0 || nx >= W || nx < 0) continue;
					if (Castle[ny][nx] != '.' && Castle[ny][nx] != '9' && Castle[ny][nx]>='0') {
						Castle[ny][nx] -= 1;
					}
					if (Castle[ny][nx] == '0') q.push(make_pair(1, make_pair(ny, nx)));
				}
			}
		}
	}
//더 이상 무너질 곳이 없을 때까지 반복.
	int cnt = 0;
	while (!q.empty()) {
		int y = q.front().second.first;
		int x = q.front().second.second;
		int time = q.front().first;
		q.pop();
        //만약 기존에 이미 파도로 바꿨었다면 패스
		if (Castle[y][x] == '.') continue;
		Castle[y][x] = '.';
        //시각 갱신
		if (cnt < time) cnt = time;
        //파도로 바뀐 곳 기준 주변 모래성 값 -1
        //만약 파도로 바뀜으로인해 무너질 곳이 생겼다면 추가.
		for (int i = 0; i < 8; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (Castle[ny][nx] >'0' && Castle[ny][nx] != '9' && Castle[ny][nx]!='.')
				Castle[ny][nx] -= 1;
			if (Castle[ny][nx] == '0') {
				q.push(make_pair(time + 1, make_pair(ny, nx)));
			}
		}
	}
	return cnt;
	
}

int main() {
	scanf("%d %d", &H, &W);
	for (int i = 0; i < H; i++) {
		scanf("%s", Castle[i]);
	}
	int cnt = timelapse();
	printf("%d", cnt);
}