토마토 [7576]

토마토 [7576]

백준 - https://www.acmicpc.net/problem/7576

7576번: 토마토

깃헙 - https://github.com/shs9509/study

문제

• 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

   

   

  

• 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다.

• 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다.

• 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다.

• 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다.

• 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

• 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라.

• 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

---

입력

• 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다.

• M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다.

• 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다.

• 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다.

• 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다.

• 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

• 토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

• 여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다.

• 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

   

   

---

풀이과정

• BFS 문제 - 나에게는 상당히 까다로웠던 문제

• 시간초과가 일어나므로 deque 를 사용하였다.

• BFS 알고리즘에서 dr dc를 이용해 사방을 탐색후 거쳐간 토마토를 '1' 로 처리해준다.

  • '1'로 처리해주는 타이밍을 사방을 탐색했을 때! 진행한다.

  • 그렇지 않으면 '시간초과' 가 일어난다.

• 좌표와 날짜를 한 튜플로 엮어서 진행했다. (x좌표, y좌표, 날짜)

   

   

깃헙에 코드!

---

느낀점

• 시간초과가 일어나 답답했던 문제

• 해결방법은 익은 토마토 처리 타이밍이었다.

• 차이점은 '1' 의 처리의 위치이다.

• 해결코드는 탐색된 사방을 '1'로 만들지만

• 문제코드는 탐색된 부분만을 '1' 로 만들기 때문에 사방탐색에서 중복으로 작업을 한다.

• 이 때문에 시간초과가 일어난다.

• 기존에는 리스트를 사용했는데 메모리적으로 튜플이 더좋다고 하여 튜플을 사용했다.

   

시행착오...

 

• pypy 를 이용하면 시간이 줄어들었지만 메모리는 오히려 늘어난다.