[백준 10711] 모래성 (C++)

문제 링크: https://www.acmicpc.net/problem/10711

10711번: 모래성

1. 주의할 점: 

- 배열의 크기가 커서 check/visit 배열을 매번 초기화해주면서 하기엔 TLE가 발생한다

- result++를 어느부분에서 할 것인지 잘 인지한다

 

2. 구현

- arr배열을 int형 배열로 받는다

- 기존에 '.'으로 입력받은 원소는 0으로 대체 + queue에 추가한다

- 매번 파도를 가지고 있지 않고 파도가 영향을 끼칠수 있는 모래성을 1씩 깍고 버린다

  -> 모래성의 강도가 0이되면 queue에 추가한다

-새로 queue에 추가된 원소가 없을 경우 종료한다

 

#include <iostream>
#include <queue>
using namespace std;
int arr[1000][1000];
int row, col, result = 0;
struct info {
	int x, y;
};
info tmp;
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { -1,-1,0,1,1,1,0,-1 };
queue<info> q;

void bfs() {
	while (1) {
		int len = q.size();
		for (int i = 0; i < len; i++) {
			int cx = q.front().x;
			int cy = q.front().y;
			q.pop();
			for (int j = 0; j < 8; j++) {
				int nx = cx + dx[j];
				int ny = cy + dy[j];
				if (nx >= 0 && ny >= 0 && nx < col && ny < row && arr[ny][nx]>0) {
					arr[ny][nx] -= 1;
					if (arr[ny][nx] == 0) {
						tmp.x = nx;
						tmp.y = ny;
						q.push(tmp);
					}
				}
			}
		}
		if (q.empty()) break;
		result++;
	}
}

int main() {
	cin >> row >> col;
	char c;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {		
			cin >> c;
			if (c == '.') {
				tmp.x = j;
				tmp.y = i;
				q.push(tmp);
				arr[i][j] = 0;
			}
			else
				arr[i][j] = c - '0';
		}
	bfs();
	cout << result;
	system("pause");
	return 0;
}