(백준 c++)7576 토마토

 

#include <iostream>
#include <queue>
#include <utility>

using namespace std;
int answer = 0, tomato = 0;
queue<pair<int, int>> q, tmp_q;
int arr[1001][1001];
bool visited[1001][1001] = {false, };

void bfs(int M, int N, pair<int, int> p)
{
	int row = p.first;
	int col = p.second;
	
	q.pop();
	//up
	if(row - 1 >= 0 && row - 1 < N && col >= 0 && col < M && visited[row - 1][col] == false)
	{
		visited[row - 1][col] = true;
		arr[row - 1][col] = 1;
		tmp_q.push(make_pair(row - 1, col));
		tomato++;
	}
	
	//down
	if(row + 1 >= 0 && row + 1 < N && col >= 0 && col < M && visited[row + 1][col] == false)
	{
		visited[row + 1][col] = true;
		arr[row + 1][col] = 1;
		tmp_q.push(make_pair(row + 1, col));
		tomato++;
	}
	
	//left
	if(row >= 0 && row < N && col - 1 >= 0 && col - 1 < M && visited[row][col - 1] == false)
	{
		visited[row][col - 1] = true;
		arr[row][col - 1] = 1;
		tmp_q.push(make_pair(row, col - 1));
		tomato++;
	}
	
	//right
	if(row>= 0 && row < N && col + 1 >= 0 && col + 1 < M && visited[row][col + 1] == false)
	{
		visited[row][col + 1] = true;
		arr[row][col + 1] = 1;
		tmp_q.push(make_pair(row, col + 1));
		tomato++;
	}

	if(q.empty())
	{
		answer++;
		q = tmp_q;
		
		while(!tmp_q.empty())
			tmp_q.pop();
	}
}

int main() {
	int num = 0;
	int M, N;
	
	cin >> M >> N;
	
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
			if(arr[i][j] == -1)
			{
				visited[i][j] = true;
				num++;
			}
		}
	}
	
	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));
				visited[i][j] = true;
				tomato++;
			}
		}
	}
	
	while(!q.empty())
	{
		bfs(M, N, q.front());
	}
	
	if(M * N - num != tomato)
		cout << -1;
	else
		cout << answer - 1;
	
	return 0;
}

BFS를 이용하여 문제를 풀었다.

처음 BFS문제를 풀어보아서 코드가 길고 푸는데 오래 걸렸다.

 

우선 M, N을 입력받고, 토마토 상자인 int형 arr 배열과 방문 여부를 나타내는 bool형 visited 배열을 선언하고,

input에 맞게 값을 넣어주도록 한다.

 

arr배열을 순회하면서 1인 부분을 확인하여 큐에 넣어주도록 한다.

그리고 visited[i][j]를 true로 바꿔주도록 한다.

tomato는 익은 토마토의 개수, num은 없는 토마토의 개수를 나타낸다.

 

이제 큐를 돌면서 bfs를 실행한다.

위, 아래, 왼쪽, 오른쪽을 확인하면서 인덱스가 0보다 크고, M, N보다 작고, 해당 visited가 false이면 tmp_q에 넣어준다.

tmp_q는 q가 비었을 때 answer++을 해주고, q에 넣어준다.(하루 계산하기 위함이다..)

q가 비었으면 tmp_q를 모두 pop하여 비어주는 작업을 한다.

 

이렇게 계속 순회하다 보면 모든 노드를 다 돌게되고

마지막에 토마토의 개수인 tomato와 M * N - num이 같은지 확인해주고,

같지 않으면 -1 리턴, 같으면 answer - 1을 리턴하도록 한다.