백준 토마토문제

https://www.acmicpc.net/problem/7576

7576번: 토마토

문제는 토마토상자에 토마토가 있을때 하루가 지날수록 토마토는 주변 토마토를 익힐수 있다. 이 때 4방향 이웃을 익히는데 익힐수 있는 모든 토마토를 다 익히는데 몇일이 걸리는지를 구하는 문제이다.

​

처음에 생각한 풀이는 하루마다 토마토상자 전체를 검사하여 익은 토마토의 주변을 익히는 방식으로 토마토판 전체를 익혔다.

​

문제에서 원하는 출력을 낼 수는 있었으나 이 방식으로는 매 반복문마다 배열 전체를 검사해야하는 단점이 있어 문제에서 요구한 시간제한 1초를 넘어버렸다.

​

따라서 시스템의 구조를 재 설계해야할 필요성을 느꼈고 BFS구조를 이용하여 재설계하였다.

 

먼저 진행했던 방법은 가장 최근에 익은 토마토를 찾아 모든 배열의 값을 검사하는 식으로 일일이 찾았으나 어디 토마토가 익어있는지를 알고 바로 찾아갈 수 있다면 더 빠르게 탐색을 마무리할 수 있다는 점에서 착안하였다.

​

BFS방식은 큐를 이용하였다.

먼저 익은 토마토가 있는곳의 위치를 큐에 넣고, 큐에서 pop 하면서 주변을 탐색한다.

탐색하면서 주변에 익지 않은 토마토가 있으면 큐에 push하기를 반복한다.

​

소스코드는 다음과 같다.

 

#include<iostream>
#include<queue>

using namespace std;

int								M, N;
int								i, j;
int								nCntNoneRipeTomato = 0;
int								nDayCnt = 0;
pair					pTmp;
queue >			qBFS;
int								nTomato[1001][1001];

void Search4Neighbor(int i, int j)
{
	if (j < M - 1 && nTomato[i][j + 1] == 0)
	{
		qBFS.push(make_pair(i, j + 1));
		nTomato[i][j + 1] = 1;
		nCntNoneRipeTomato--;
	}

	if (j > 0 && nTomato[i][j - 1] == 0 )
	{
		qBFS.push(make_pair(i, j - 1));
		nTomato[i][j - 1] = 1;
		nCntNoneRipeTomato--;
	}

	//뒤
	if (i > 0 && nTomato[i - 1][j] == 0 )
	{
		qBFS.push(make_pair(i-1, j));
		nTomato[i-1][j] = 1;
		nCntNoneRipeTomato--;
	}

	//앞
	if (i < N - 1 && nTomato[i + 1][j] == 0 )
	{
		qBFS.push(make_pair(i + 1, j));
		nTomato[i+1][j] = 1;
		nCntNoneRipeTomato--;
	}

}

int main() {

	//입력받기
	// M : j , N : i
	cin >> M >> N;
	for (i = 0; i < N; i++)
		for (j = 0; j < M; j++)
		{
			cin >> nTomato[i][j];
			if (nTomato[i][j] == 0)
				nCntNoneRipeTomato++;
			else if (nTomato[i][j] == 1)
			{
				qBFS.push(make_pair(i, j));
			}
			
		}

	int nQueSize = 0;
	while (!qBFS.empty())
	{
		nQueSize = qBFS.size();
		while (nQueSize--)
		{
			pTmp = qBFS.front();
			qBFS.pop();
			Search4Neighbor(pTmp.first, pTmp.second);
		}
		nDayCnt++;

		//디버깅용
		//토마토판 상황 출력
		/*
		for (i = 0; i < N; i++)
		{
			for (j = 0; j < M; j++)
			{
				cout << nTomato[i][j] << ' ';
			}
			cout << endl;
		}
		cout << "몇일후??" << nDayCnt << endl;
		cout << "안익은 토마토개수??" << nCntNoneRipeTomato << endl;
		*/
	}

	if (nCntNoneRipeTomato != 0)
	{
		cout << -1;
		return 0;
	}

	cout << --nDayCnt;

	return 0;
}