주변에 익은 토마토가 있다고 해서 왜 다시 큐에 넣어주셨나요?

예를 들어 2일차일 때 익은 토마토는 q에 넣었고 익은 토마토에 영향으로 익을 토마토 (3일차에 익은 토마토)는 q_에 넣어서 풀려고했습니다.

그러면 4일차 이후는 어떻게 되나요? 이렇게 큐에 새롭게 들어가는 토마토들에 대한 방문 체크는 하지 않아도 괜찮은 걸까요?

36번째 줄과 40번째 줄에서 방문 체크가 이루어지고 있는 것 아닌가요?  

방문 체크를 하고는 있으나, 44번째 줄에서는 순서가 잘못됐습니다. BFS에서는 반드시 큐에 넣는 순간에 방문 체크를 해야 중복 방문이 일어나지 않습니다. 큐에서 뺀 뒤에서야 체크하면, 여러 방향에서 동시에 같은 좌표를 큐에 넣는 동안 막아서는 장치가 없게 되므로, 이를 반복하게 되면 결국 지수 시간 복잡도를 가지게 됩니다. 왜 40번째 줄과는 달리 44번째 줄에서는 바로 방문 체크를 하지 않으셨는지, 그 차이를 둔 의미를 모르겠습니다.

그보다도 저는 이 코드의 전체적인 로직의 흐름에 대해 묻고 싶습니다. 다시 여쭤보는데, 굳이 큐를 2개로 나눠서 진행해야 할 이유가 있나요? 맨 처음에 익어있던 토마토라면 처음에 큐에 바로 넣어줬을 거고, 이후에 익게 되는 토마토는 그걸 익게 만드는 토마토가 큐에 넣어줬을 텐데, 이미 익어있는 토마토를 주변에서 발견했다고 해서 큐에 다시 넣으려고 할 필요가 있는지를 묻는 것입니다.

우선,  말씀하신 대로 방문테크하는 순서를 변경함으로 해서 문제를 맞췄습니다. 그리고 토마토가 다 익을 때까지 며칠걸리는지 계산하는데 큐 2개가 필요하다고 생각했습니다.  하나의 큐 q에는 당일날 익은 (그전날에는 익지 않은) 토마토를 넣었고 q_에는 당일날 익은 (그전날에는 익지 않은) 토마토에 의해 익은 토마토를 넣었습니다. 이미 익어있는 토마토를 큐에 넣으려고 하지는 않았습니다.  

맞히셨다니 다행입니다. 이제 다른 분들 코드를 보시면서, 왜 제가 큐가 여러 개 있는 것을 불필요하다고 말씀드린 것인지 확인해보시면 좋을 것 같습니다.

감사합니다! 큐가 하나만 있어도 풀 수 있는 문제였네요. 큐 한개만 이용하는 방식으로 다시 풀어보도록 하겠습니다.