[C++/알고리즘] 백준 7576 (토마토)

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

7576번: 토마토

 

 

BFS로 풀면 되는 문제이다. 

우선 토마토에 대한 정보를 입력받고 

	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			if (arr[i][j] == 1) {
				check[i][j] = true;
				q.push(make_pair(i, j));
			}
		}
	}

처음에 전체 토마토 상자를 보면서 안에 익은 토마토가 어느 위치에 있는지 찾고 queue에 넣어주었다.

 

그후 while문으로 들어가서 현재 queue의 size만큼 for문을 돌려주면서 해당 위치의 동, 서, 남, 북의 칸을 비교해서

익지 않은 토마토(arr[y][x] == 0)이며 방문하지 않았으면(check[y][x] == false) queue에 넣고 방문했다는 표시를 한다.

 

for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			if (arr[i][j] == 0 && check[i][j] == false)
			{
				return -1;
			}
		}
	}

이 부분은 처음에 런타임 에러도 발생하고 채점 결과가 틀렸다고 계속 나와서

Visual studio에서 예제를 돌렸을 때는 문제가 없어서 뭐가 문제인지 한참 고민하다가 

예를 들면 3x3 에서

0	-1	-1
-1	1	1
1	1	1

이렇게 예상치 못한 상황에서 익지 못하게 되는 토마토를 확인하기 위해서 추가하게 되었다. 

 

#include <iostream>
#include <queue>

using namespace std;
const int MAX_BOX = 1000;
int dirX[4] = { 1, -1, 0, 0 };
int dirY[4] = { 0,0,-1,1 };
bool check[MAX_BOX + 1][MAX_BOX + 1];

int tomato(int **arr, int w, int h)
{
	int day = 0;
	queue<pair<int, int>> q;

	// 처음에 넘겨받은 토마토 상자 안에 익은 토마토가 몇 개나 있는지 
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			if (arr[i][j] == 1) {
				check[i][j] = true;
				q.push(make_pair(i, j));
			}
		}
	}

	while (!q.empty())
	{
		int q_size = q.size();
		for (int j = 0; j < q_size; j++) {

			int y = q.front().first;
			int x = q.front().second;

			q.pop();

			for (int i = 0; i < 4; i++)
			{
				int tempy = y + dirY[i];
				int tempx = x + dirX[i];

				if ((tempy < h && tempy >= 0) && (tempx >= 0 && tempx < w)) {
					if (arr[tempy][tempx] == 0 && check[tempy][tempx] == false)
					{
						check[tempy][tempx] = true;
						q.push(make_pair(tempy, tempx));
					}
				}
			}
		}
		day += 1;
	}

	// 다 돌아봤을 때 익지 않은 토마토가 존재하면서 그곳에 방문하지 않은 경우가 있는지 확인
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			if (arr[i][j] == 0 && check[i][j] == false)
			{
				return -1;
			}
		}
	}
	return day - 1;
}

int main()
{
	int w, h;
	cin >> w >> h;

	// 배열
	int **box = new int*[h];
	for (int i = 0; i < h; i++)
	{
		box[i] = new int[w];
	}

	// 입력받기
	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			cin >> box[i][j];
		}
	}
	cout << tomato(box, w, h);
	return 0;
}