[BOJ 10711] 모래성 C++

 

10711번: 모래성

 

 

문제풀이

 

처음 시도했을 때는 모래성을 모두 queue에 넣고 8방향을 모두 살펴 무너지는지 확인 후 무너지지 않는 모래성을 queue에 다시 넣어줬다.

 

결과는 시간초과..

 

#include <iostream>
#include <queue>
#define MAX 1001
using namespace std;

int h, w;
int map[MAX][MAX];
bool visited[MAX][MAX];

int dx[] = { -1, 1, 0, 0, -1, -1, 1, 1 };
int dy[] = { 0, 0, -1, 1, -1, 1, -1, 1 };

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

	cin >> h >> w;

	queue<pair<int, int>> q;
	string tmp;

	for (int i = 0; i < h; i++) {
		cin >> tmp;
		for (int j = 0; j < w; j++) {
			map[i][j] = tmp[j] != '.' ? tmp[j] - '0' : 0;
			if (map[i][j] != 0) {
				q.push({ i, j });
				visited[i][j] = true;
			}
		}
	}

	int answer = 0;

	while (!q.empty()) {
		int size = q.size();
		for (int i = 0; i < size; i++) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();

			int cnt = 0;
			for (int j = 0; j < 8; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];

				if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
				if (visited[nx][ny]) continue;

				if (map[nx][ny] == 0)
					cnt++;
			}

			if (cnt < map[x][y])
				q.push({ x, y });
			else
				map[x][y] = 0;
		}

		if (q.size() == size)
			break;
		
		answer++;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] == 0)
					visited[i][j] = false;
			}
		}
	}
	cout << answer;

	return 0;
}

 

 

그래서 무너지지 않는 모래성이 아니라 무너지는 모래성을 queue에 넣어줬다.

 

모래성의 튼튼함은 1부터 9사이의 숫자로 표현되는데 튼튼함이 9이면 절대 무너지지 않는다.

따라서 1부터 8까지의 튼튼함을 가지는 모래성들은 queue에 넣는다.

 

그 모래성들의 8방향을 모두 살펴보고 근처에 무너지는 모래성이 있다면 queue에 넣어준다.

이 과정을 무너지는 모래성이 없을 때까지 반복해준다.

 

 

C++ 코드