토마토
-
[백준 7576번] 토마토 (자바)Algorithm/BFS 2022. 5. 13. 21:46
백준알고리즘 7576번 : 토마토 (Solved.ac 난이도 Gold5) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 전형적인 BFS문제이다만.. 나는 DFS로 몇 번 시도해보고서야 완전 틀린 해석이었다는 걸 깨달았다. DFS로 하게되었을 때의 문제점이라면, 각 구역마다 한번의 탐색으로 끝내도 될 것을 계속 접근하여 비효율적으로 만드는 것이다. 잘 익은 토마토를 기준으로 너비 우선탐색으로 뻗어나가면, 애초에 검증이 많이 필요..