[백준 10711] 모래성

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

10711번: 모래성

#include <cstdio>
#include <queue>
#include <cstring>
int R, C;
char board[1000 + 2][1000 + 2];
int A[1000 + 2][1000 + 2];

struct _st
{
	int x, y;
};
std::queue<_st> Q;	// 큐 안에는 "모래"가 담겨있다. 
std::queue<_st> Buffer;



void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 0; i < R; i++) {
		scanf("%s", &board[i]);
		for (int j = 0; j < C; j ++) {
			if (board[i][j] == '.') {	// 모래를 기준으로 생각해야 시간초과 나지 않는다 !
				Q.push({ i, j });
				A[i][j] = 0;
			}
			else A[i][j] = board[i][j] - '0';
		}
	}
}


void chk_sand()
{
	// dir
	int dir_x[8] = { 1, 1, 1, 0, 0, -1, -1, -1 };
	int dir_y[8] = { 0, 1, -1, -1, 1, 0, 1, -1 };

	Buffer = {};

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 8; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (A[nx][ny] == 0) continue;
			if (A[nx][ny] > 0 ) {
				A[nx][ny] -= 1;
				if (A[nx][ny] == 0) Buffer.push({ nx, ny });
			}
		}
	}
	Q = Buffer;
}


int Flood_Fill()
{
	int wave = 0;
	while (1) {
		chk_sand();
		if (Q.empty()) return wave;	// 더이상 모래가 되는 애가 없다면
		wave++;
	}
}


int main()
{
	input();
	int ans = Flood_Fill();
	printf("%d\n", ans);
	return 0;
}

 

'시간초과' 3번은 모래성을 기준으로 (1) Flood-Fill + 맵복사 / (2) 버퍼큐 + 맵복사 / (3) 큐 + 벡터에 0되는 좌표 저장 후 0으로 변경하는 방식을 사용했었다. 

이렇게 구현하면 불필요한 연산이 많아지는데, 그 이유는 모래성을 기준으로 파도가 밀려올 때 마다 주변을 다 탐색해야 하기 때문이다. 이전 탐색 때 0이었던 곳은 새로운 탐색 때도 0이다. 따라서 BFS를 돌리면서 새롭게 0이 되는 곳 만 버퍼큐에 넣어주고, 큐를 계속 갱신하는 과정을 거친다면 이전에 탐색했던 곳을 중복으로 탐색하는 것을 막을 수 있다. 

 

 

따라서 가장 처음 맵을 입력받을 때, 0인 좌표를 Q에 저장한다. 

이후 BFS 탐색을 통해 인접 8구역에 모래가 있다면 1을 감소시킨다. 만약 이렇게 감소시킨 모래가 0이 된다면 버퍼큐에 저장하고, 값 리턴 전 Q에 복사한다. 

만약 BFS 함수가 리턴한 Q의 사이즈가 0이면, 0이되는 모래가 없다는 뜻이므로 모래성의 모양이 더 이상 변화하지 않게 된다는 의미와 같다. 

 

---

++22.11.09 갱신

1000 * 1000 맵이므로 while 루프를 여러번 돌리면 시간 초과날 확률이 굉장히 크다.

따라서 BFS를 한번만 돌리고 값을 구하려고 해야한다. 

생각하자 생각.. 맵 사이즈가 이렇게 커지면 완전탐색으로는 타임아웃 난다. 

그리고 컨테이너 안에 어떤 정보가 담겨 있는지 잘 생각하자. 

#include <cstdio>
#include <queue>
#include <cstring>
int R, C;
char board[1000 + 2][1000 + 2];
int A[1000 + 2][1000 + 2];

struct _st
{
	int x, y;
	int time;
};
std::queue<_st> Q;	// 큐 안에는 "모래"가 담겨있다. 


void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 0; i < R; i++) {
		scanf("%s", &board[i]);
		for (int j = 0; j < C; j ++) {
			if (board[i][j] == '.') {	// 모래를 기준으로 생각해야 시간초과 나지 않는다 !
				Q.push({ i, j, 0 });
				A[i][j] = 0;
			}
			else A[i][j] = board[i][j] - '0';
		}
	}
}


int BFS()
{
	// dir
	int dir_x[8] = { 1, 1, 1, 0, 0, -1, -1, -1 };
	int dir_y[8] = { 0, 1, -1, -1, 1, 0, 1, -1 };

	_st data = {};
	while (!Q.empty()) {
		data = Q.front();
		Q.pop();

		for (int p = 0; p < 8; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (A[nx][ny] == 0) continue;
			if (A[nx][ny] > 0 ) {
				A[nx][ny] -= 1;
				if (A[nx][ny] == 0) Q.push({ nx, ny, data.time + 1 });
			}
		}
	}
	return data.time;
}



int main()
{
	input();
	int ans = BFS();
	printf("%d\n", ans);
	return 0;
}