[C++] 백준 7576 토마토

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
int M = 0;
int N = 0;
int iDirX[4] = { 1, -1, 0, 0 };
int iDirY[4] = { 0, 0, 1, -1 };
int iBox[1001][1001] = {};
bool bVisit[1001][1001] = {};
 
int main()
{
	std::queue<std::pair<int, int>> que = {};
	std::queue<std::pair<int, int>> next_que = {};
 
	std::cin >> M >> N;
 
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			std::cin >> iBox[i][j];
 
			if (iBox[i][j] == 1)
			{
				que.push({ i,j });
				bVisit[i][j] = true;
			}
		}
	}
 
	int iCount = 0;
 
	while (!que.empty())
	{
		while (!que.empty())
		{
			int iX = que.front().first;
			int iY = que.front().second;
			que.pop();
 
			for (int i = 0; i < 4; ++i)
			{
				int iNextX = iX + iDirX[i];
				int iNextY = iY + iDirY[i];
 
				if (iNextX >= 0 && iNextX < N &&
					iNextY >= 0 && iNextY < M)
				{
					if (!bVisit[iNextX][iNextY] && !iBox[iNextX][iNextY])
					{
						iBox[iNextX][iNextY] = 1;
						bVisit[iNextX][iNextY] = true;
						next_que.push({ iNextX, iNextY });
					}
				}
			}
		}
 
		que = next_que;
 
		while (!next_que.empty())
		{
			next_que.pop();
		}
 
		if (!que.empty())
			++iCount;
	}
 
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (!iBox[i][j])
			{
				std::cout << -1;
				return 0;
			}
		}
	}
 
	std::cout << iCount;
 
	return 0;
}

이중큐를 이용해서 문제 풀었습니다.

계속해서 퍼져나가야하기 때문에 이중큐를 이용해서 한번씩 넓어지게 만들었습니다.

큐의 싸이즈를 이용해서 하나의 큐만을 이용하는 방법도 있습니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
int M = 0;
int N = 0;
int iDirX[4] = { 1, -1, 0, 0 };
int iDirY[4] = { 0, 0, 1, -1 };
int iBox[1001][1001] = {};
bool bVisit[1001][1001] = {};
 
int main()
{
	std::queue<std::pair<int, int>> que = {};
 
	std::cin >> M >> N;
 
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			std::cin >> iBox[i][j];
 
			if (iBox[i][j] == 1)
			{
				que.push({ i,j });
				bVisit[i][j] = true;
			}
		}
	}
 
	int iCount = 0;
 
	while (!que.empty())
	{
		int iSize = que.size();
 
		for (int j = 0; j < iSize; ++j)
		{
			int iX = que.front().first;
			int iY = que.front().second;
			que.pop();
 
			for (int i = 0; i < 4; ++i)
			{
				int iNextX = iX + iDirX[i];
				int iNextY = iY + iDirY[i];
 
				if (iNextX >= 0 && iNextX < N &&
					iNextY >= 0 && iNextY < M)
				{
					if (!bVisit[iNextX][iNextY] && !iBox[iNextX][iNextY])
					{
						iBox[iNextX][iNextY] = 1;
						bVisit[iNextX][iNextY] = true;
						que.push({ iNextX, iNextY });
					}
				}
			}
		}
 
		if (!que.empty())
			++iCount;
	}
 
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (!iBox[i][j])
			{
				std::cout << -1;
				return 0;
			}
		}
	}
 
	std::cout << iCount;
 
	return 0;
}

메모리가 바로 줄어드는 것을 확인했습니다.