23. DFS와 BFS
CLASS 3 ESSENTIAL
사각형 격자에 토마토가 들어있을 때 모든 토마토가 익는 데에 걸리는 시간을 구하는 문제입니다. 문제가 생긴게 BFS를 쓰기 좋게 생겼는데, 익은 토마토를 시작점으로 하여 주위의 토마토가 익는 데에 걸리는 시간을 구하면 됩니다. 다만, 각 토마토에 대해 각각 BFS를 돌리면 시간 상 문제가 생길 수가 있습니다. 따라서 익은 토마토의 위치를 모두 기억해놓고, BFS를 돌릴 큐에 모든 익은 토마토 위치를 집어넣고 BFS를 한번에 돌리면 시간을 절약할 수 있습니다.(ex) 14, 7 거리의 BFS 돌릴거 7, 7로 줄일 수 있습니다.)
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| C++ | 코드(Github) / 코드(백준) | 2020-12-21 23:55:57 |