[백준] 7576번 - BFS 토마토 전이

	for (int i = 0; i < sero; i++)
	{
		for (int j = 0; j < garo; j++)
		{
			if (danji[i][j] == 1)//danji: 토마토 박스
			{			
				pos = { j,i };
				q.push(pos);
			}				
		}
	}

 

 

익은 모든 토마토들이 전이를 동시에 시작하므로 큐에 익은 토마토들을 넣어준다.

 

void nSearch()
{
	while (q.empty() == false)
	{	
		pos = q.front();
		q.pop();	
		discovered[pos.y][pos.x] = true;
		for (int i = 0; i < 4; i++)
		{
			Pos next = pos + front[i];

			if (!CanGo(next))
				continue;		
			if (discovered[next.y][next.x])
				continue;
			danji[next.y][next.x] = danji[pos.y][pos.x]+1;			
			q.push(next);
		}		
	}
}

 

그 후 BFS를 하는데 몇 일차에 익었는지에 따라 번호를 부여한다. 번호는 자기 부모 + 1이다.

 

	for (int i = 0; i < sero; i++)
	{
		for (int j = 0; j < garo; j++)
		{
			if (danji[i][j] == 0)
			{
				cout << -1;
				return 0;
			}

			if(num<danji[i][j])
			{
				num = danji[i][j];
			}
		}
	}
	cout << num-1;

 

BFS 후에도 토마토박스에 안익은 토마토(0)가 남아있다면 -1을 출력하고 아니라면 num과 토마토 박스의 숫자를 비교해서

가장 큰 숫자에 1을 뺀 것이 모든 토마토가 익는데 걸리는 일 수이다. 처음부터 모든 토마토가 익을 경우 0을 출력해야 하는데 그러면 토마토 박스의 숫자들이 모두 1로 통일될 것이므로 자동으로 0이 출력된다.