7576 - 토마토

문제 요약

1. N x M 판에 토마토가 들어있다.
2. 1은 익은 토마토를 나타내고 0은 안익은 토마토를 나타내며, -1은 토마토가 들어있지 않은 칸이다.
3. 1초가 지날때 마다 익은 토마토를 기준으로 상하좌우에 있는 토마토가 익는다.
4. 몇초가 지나야 토마토가 다 익는지 출력하시오 (단, 토마토가 모두 익을 수 없다면 -1을 출력)

접근법

이 문제 또한 BFS를 사용하면 매우 쉽게 풀수 있는 문제다. 기존 미로탈출 문제와 90% 같다고 생각하면 된다. 유일한 차이점이 있다면 미로 탈출에서는 방문했던 지점을 다시 방문하지 않기 위해 별도의 배열을 만들어 방문 내역을 관리했다면, 이번문제에서는 굳이 다른 별도의 배열을 만들지 않더라도 토마토 판의 값을 0에서 1로 바꿔주면 해당 칸은 이미 방문했다는 뜻이 되기 때문에 별도의 배열을 만들어주지 않아도 된다.

이 문제를 풀기 위해 추가적으로 고려해줘야 하는 상황은 과연 판위에 모든 토마토가 다 익을 수 있는지에 대한 여부이다.
|Tomato|Tomato|Tomato|
|—|—|—|
| 0| -1| 0|
| -1| -1| 0|
| 0| 0| 1|

토마토가 위와 같은 형태로 판에 놓여 있다면 판 위에 (0, 0) 위치에 있는 토마토는 1,000년이 지나도 익지 않을 것이다. (0, 0) 주변에 토마토가 놓여있지 않기 때문이다. 그럼 언제까지 BFS 탐색을 해야 토마토가 다 익었는지, 다 익을 수 없는 배치인지를 확인할 수 있을까?

정답은 더이상 BFS로 탐색할 칸이 없을 때 안 익은 토마토가 있는지 확인하는 것이다. 이 문제 역시 안 익은 토마토에 대해서만 BFS 탐색을 진행하기 때문에 더이상 BFS로 탐색할 내용이 없다면, 모든 토마토가 익었거나 익을 수 없는 토마토가 있다는 것을 의미한다. 따라서 BFS가 다 끝난뒤 안 익은 토마토가 있는지 여부만 체크하면 된다.

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)