[백준 7576] 토마토

전형적인 완전탐색 BFS 문제

 

초반에는 시작점을 최신화 하지 않고 항상 1번째 날 시작점 그대로 사용해서 제출했는데 시간초과남

그래서 매번 BFS돌때마다 최신화된 시작점 즉 새로운 최전방의 시작점들을 저장해

다음 BFS때 해당 시작점들에서만 4방향으로 확인하게 함

 

---

#include <iostream>
#include <queue>
#include <algorithm>
#define SIZE 1000

using namespace std;

int arr[SIZE][SIZE];
int N, M;
queue<pair<int,int>> start;

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

bool check() {
	for (int i = 0; i < M; i++) {
		for (int k = 0; k < N; k++) {
			if (arr[i][k] == 0) {
				return false;
			}
		}
	}
	return true;
}

void bfs() {
	queue<pair<int, int>> newstart;

	while(!start.empty()) {
		int starty = start.front().first;
		int startx = start.front().second;
		start.pop();

		// 4방향에 대해 조사
		for (int i = 0; i < 4; i++) {
			int newy = starty + dy[i];
			int newx = startx + dx[i];

			if (newx < 0 || newx >= N || newy < 0 || newy >= M) continue;
			else {
				if (arr[newy][newx] == 0) {
					arr[newy][newx] = 1;
					// 다음 턴 시작점들
					newstart.push(make_pair(newy, newx));
				}
			}
		}
	}
    
	start = newstart;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		for (int k = 0; k < N; k++) {
			cin >> arr[i][k];
			if (arr[i][k]==1) start.push(make_pair(i, k));
		}
	}

	int day = 0;
	while (!check()) {
		bfs();
		if (start.empty()) {
			cout << -1;
			return 0;
		}
		day++;
	}
	cout << day;
	return 0;
}