BOJ_7576_토마토

1.

구분: DFS, BFS

언어: Python

전략: 

• BFS를 통해 전체 그래프를 모두 탐색
• 큐에 토마토의 좌표와 며칠인지를 append한다. -> (x,y,day)
• 큐에서 popleft()하여 나온 칸과 인접한(상, 하, 좌, 우) 칸이 안익은 토마토이고, 칸의 범위를 벗어나지 않았다면, 날짜를 +1하여 큐에 넣는다 -> (x,y,day++) ** 단! 동시 다발적으로 토마토가 익기 때문에 day의 초기화가 필요하다
• 큐가 빌때까지 위의 과정을 반복한다.
• 전체를 돌면서 만약 안 익은 토마토가 존재하는지 확인한다.

복잡도:

시간- 1000*1000 = 10^6 -N과 M이 최대 1000이기 때문에 

공간 - 최대 10^6 만큼 입력을 받으니 그것을 받을 크기의 큐 

---

2.코드

입력을 받고, 최초의 토마토를 큐에 넣는다

큐가 빌 때까지 날들을 더한다

 

---

3. 

• 2차원 배열의 x, y가 너무 혼란을 주었다. 계속 array범위를 벗어났다는 오류를 받았다. 확실한 나만의 기준을 정해야 겠다.
• day도 함께 큐에 append하는 방법은 아빠가 아이디어를 준 것이다. 그 전에는 큐를 여러 개 사용하는 생각을 했는데, 결국 마지막에 day를 구할 때, 곤란했었다. 
• DFS로도 한번 풀어봐야겠다.