안녕하세요? 반례 드립니다:

입력:
5 1
1 0 -1 0 0
정답:
-1
출력:
1

토마토가 없는 칸이 중간에 하나 있기 때문에 토마토가 없는 칸 이후의 토마토는 익지 못하므로 -1을 출력하는 것이 정답입니다.

토마토가 모두 익지 않음에도 출력이 -1이 나오지 않는 것은 30번째 줄부터 시작하는 토마토가 익었는지를 판단하는 함수 부분에서 문제가 생겨서 그런 것 같습니다. 논리대로라면 토마토가 익지 않을 것이 확실해 -1을 출력해야 하는 경우는 아래와 같을 것입니다:

- 검사하고자 하는 칸이 익지 않은 토마토(0)이면서, 상하좌우에 모두 토마토가 없을 경우(-1)

하지만 이 경우에는 반례와 같이 익은 토마토와 익지 않은 토마토가 서로 떨어져 있으면서 익지 않은 토마토가 여러 개 인접해 있을 경우 익지 못함에도 불구하고 익을 수 있는 토마토로 판단하게 됩니다.

힌트를 하나 드려볼까요? 토마토가 시간이 지나면서 익는 과정을 반복하다가, 어느 순간 토마토가 더 이상 익지 않는 시점이 생길 것입니다. 토마토가 더 이상 익지 않는다는 것은, 둘 중 하나의 상황을 의미하죠: 1) 토마토가 모두 익어서 더 익을 토마토가 없거나, 2) 익지 않은 토마토와 익은 토마토가 인접해 있지 않아 더 이상 익을 수 있는 토마토가 없는 경우.

모든 토마토가 익을 수 있는지의 여부를 판단하는 것은 바로 토마토가 더 이상 익지 않아 그래프에 변화가 없는 경우일 것입니다. 그래프에 변화가 더 이상 없음에도 익지 않은 토마토가 있다는 것이 어떤 의미인지 한 번 생각해 보세요.

문제가 해결되기를 바랍니다!

그건 생각 못했었네요 감사합니다 ㅠㅠ