[백준 C++] 7576 토마토 - 너비우선탐색

7576번: 토마토

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

vector<vector<int>> Box;
queue<pair<int, int>> Queue1;
queue<pair<int, int>> Queue2;

int BFS(int N, int M)
{
	int Day = 0;

	while (true)
	{
		while (!Queue1.empty())
		{
			int Row = Queue1.front().first;
			int Col = Queue1.front().second;
			Queue1.pop();

			// Left
			if (Col > 0
				&& Box[Row][Col - 1] == 0)
			{
				Box[Row][Col - 1] = 1;
				Queue2.emplace(Row, Col - 1);
			}

			// Top
			if (Row > 0
				&& Box[Row - 1][Col] == 0)
			{
				Box[Row - 1][Col] = 1;
				Queue2.emplace(Row - 1, Col);
			}

			// Right
			if (Col < M - 1
				&& Box[Row][Col + 1] == 0)
			{
				Box[Row][Col + 1] = 1;
				Queue2.emplace(Row, Col + 1);
			}

			// Bottom
			if (Row < N - 1
				&& Box[Row + 1][Col] == 0)
			{
				Box[Row + 1][Col] = 1;
				Queue2.emplace(Row + 1, Col);
			}
		}

		if (Queue2.empty())
		{
			return Day;
		}

		++Day;

		while (!Queue2.empty())
		{
			int Row = Queue2.front().first;
			int Col = Queue2.front().second;
			Queue2.pop();

			// Left
			if (Col > 0
				&& Box[Row][Col - 1] == 0)
			{
				Box[Row][Col - 1] = 1;
				Queue1.emplace(Row, Col - 1);
			}

			// Top
			if (Row > 0
				&& Box[Row - 1][Col] == 0)
			{
				Box[Row - 1][Col] = 1;
				Queue1.emplace(Row - 1, Col);
			}

			// Right
			if (Col < M - 1
				&& Box[Row][Col + 1] == 0)
			{
				Box[Row][Col + 1] = 1;
				Queue1.emplace(Row, Col + 1);
			}

			// Bottom
			if (Row < N - 1
				&& Box[Row + 1][Col] == 0)
			{
				Box[Row + 1][Col] = 1;
				Queue1.emplace(Row + 1, Col);
			}
		}

		if (Queue1.empty())
		{
			return Day;
		}

		++Day;
	}
}

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

	int M, N;
	cin >> M >> N;

	Box.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		Box.emplace_back(vector<int>());

		for (int j = 0; j < M; ++j)
		{
			int Tomato;
			cin >> Tomato;
			Box.back().emplace_back(Tomato);

			if (Tomato == 1)
			{
				Queue1.emplace(i, j);
			}
		}
	}

	int Day = BFS(N, M);
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (Box[i][j] == 0)
			{
				Day = -1;
				cout << Day;
				return 0;
			}
		}
	}

	cout << Day;
}

---

 

BFS 문제입니다.

두 개의 큐를 사용해서 하루에 익는 토마토를 번갈아가면서 탐색하도록 했습니다.

한 쪽 큐를 모두 탐색하면 하루가 증가하고 다른 큐로 넘어가는 방식입니다.

 

다른 분들의 풀이를 보니 큐 한 개로 탐색하면서

테이블에 각 토마토가 몇번째 날에 익었는지를 저장해서 푸는 방법도 존재했습니다.