[BOJ]7576-토마토

7576

토마토 숙성시간을 찾는 문제

오랜만에 푸는 백준 문제 다 까먹어버렸다. ㅎㅎ

여러 시도를 했는데 처음에는 배열 3개로 풀었는데 시간초과가 나버려서 찾아봤더니 질문 게시판에서 bfs임을 알게 되었다.

그래서 bfs를 구현했는데 하루가 지나고 시작하는 탐색을 따로 for문으로 다 돌았더니 시간이 부족해서 다 구간만 끊어서 queue에 넣어버렸다.

성공 코드

#include <iostream>
#include <queue>
using namespace std;

int arr[1001][1001];
int visited[1001][1001];
int M, N;

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

queue<pair<int, int>> q;

bool checkZero()
{
	bool flag = false;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (arr[i][j] == 0)
			{
				flag = true;
				
				break;
			}
		}
		if (flag) break;
	}

	return flag;
}

bool check4dir(int x, int y)
{
	bool check = false;
	//2. 토마토 주변 토마토 찾기
	
	for (int i = 0; i < 4; i++)
	{
		int tmpX = x + dx[i];
		int tmpY = y + dy[i];

		if (tmpX >= 0 && tmpX < N && tmpY >= 0 && tmpY < M)
		{
			//4. 퍼트리기
			if (visited[tmpX][tmpY] == 0 && arr[tmpX][tmpY] == 0)
			{
				arr[tmpX][tmpY] = 1;

				q.push(make_pair(tmpX, tmpY));

				check = true;
			}
		}
	}

	return check;
}

void search()
{
	if (q.empty()) // 탐색 완료
	{
		return;
	}
	else
	{
		// 탐색
		bool flag = false;
		int size = q.size();
		for(int i=0; i < size; i++)
		{
			pair<int, int> loc = q.front();
			q.pop();
			visited[loc.first][loc.second] =1;

			if (check4dir(loc.first, loc.second))
			{
				flag = true;
			}
		}

		if (flag)
		{
			days += 1;
			search();
		}
		
	}
}

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

	cin >> M >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
		}
	}

	if (checkZero() == false) // 이미 다 익었을 때
	{
		cout << 0;
	}
	else
	{
		// 1. 익은 토마토 찾기(처음)
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				
				if (arr[i][j] == 1)
				{
					q.push(make_pair(i, j));
				}
			}
		}

		search();

		if (checkZero())
		{
			cout << -1;
		}
		else
		{
			cout << days;
		}
	}

}