백준 7569: 토마토 (Swift)

토마토 시리즈 중 3차원의 토마토 문제이다.

기존의 전형적인 2차원 배열에서 앞,뒤,좌,우를 체크하는 bfs와 동일한 알고리즘을 3차원으로 확장시켜 탐색하는 문제이다.

즉, 앞,뒤,좌,우,상,하    총 6방향을 체크하면 된다.

 

문제의 포인트 두가지는,

 

- 1. 초기 토마토 모아놓고 시작하기

3차원 배열을 탐색하다가 "익은 토마토" (1)을 만났을 때,  더이상 뻗어나갈 수 없을 때까지 쭉 탐색을 하게되면, 

a,b토마토가 5일 씩 전파하여 끝날 것을 a토마토 하나만 전파하여 10일이 걸리도록 탐색하는 경우가 생길 수 있으므로,

 

초기에 전체 배열을 한 번 탐색하여 토마토의 위치를 (queue로 사용할) Array에 모아놓은 후, 

하나씩 pop하며 bfs를 진행하면 된다.

 

-2. 초기 토마토 모아놓으며, 배열내 0 ( 익지 않은 토마토 )의 갯수도 세어 놓는다.

 

초기 익지않은 토마토의 갯수를 세놓은 후, bfs가 진행되며 0이 1로 변하는 ( 토마토가 익게 되는) 경우마다 0의 갯수를 1씩 줄여나간다.

bfs가 모두 끝난 후 0의 갯수가 0이 되면 모든 토마토가 익은 것이므로 소요된 일수를 return하면되고,

0의 갯수가 0보다 크다면, 어떤 토마토는 익지 못하고 끝난 것이므로, -1을 return한다.

 

 그렇게 하는 이유는, bfs가 끝나고 다시 배열 전체를 탐색하며 0이 있는지 체크하는 것은 소모적이기 때문.