백준 7576 - 토마토

🔐 백준 7576 - 토마토

https://www.acmicpc.net/problem/7576

🔑 풀이

상자 속 토마토가 모두 익을 때까지의 최소 일수를 구하는 문제이다.

이는 시작점에서 모든 지점까지의 거리를 구하는 BFS 문제와 같다.

처음 문제를 풀때는 주어지는 M * N 칸에 대해 1인 경우(익은 토마토)를 하나씩 BFS를 돌리는

방식을 구현하였다. 또한 각각의 익은 토마토에 대해 거리를 구하므로, 칸마다 거리 배열을 초기화시켜 주었다.

하지만 이러한 방식으로 구현할 경우 문제의 예제 3에 대해 다음과 같은 결과를 내놓게 된다.

위의 방식으로는 최소 날짜를 구하기 힘드므로, 다른 방식으로 풀어야 한다.

다른 방법으로 토마토들의 정보를 입력받을 때, 익은 토마토의 경우 그 즉시 큐에 넣는 방법이 있다.

이 방식으로 BFS를 수행할 경우 다음과 같은 과정에 따라 옳은 답을 도출할 수 있다.

익은 토마토를 모두 큐에 넣은 후 BFS를 실행하면 시작점이 여러 개인 상태로 BFS를

순차적으로 실행하여 각 칸의 최소 날짜를 구할 수 있다.

그 후, 만약 방문하지 않은 칸(익지 못하는 토마토)이 있는 경우 -1을 출력하고, 다 익었다면

최대 거리를 출력한다.

🧩코드