[파이썬] 백준 7576번: 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

처음 이 문제를 보고 이거도 너무나 당연한 BFS, DFS문제라고 생각했다. 그러고 제출을 했는데 허무하게도 "시간초과"가 떠버렸다.

왜 시간초과가 떴을까? 몇 가지 추측을 해보았다.

1. 입력을 생으로 for문으로 받고 bfs를 돌릴때도 하나하나 다 돌렸기 때문일 수 도 있을 것이다.

  --> 해당 문제를 해결하기 위해 입력을 받으면서 1일 경우 큐에 넣어주는 작업까지 처리를 해 주었다.

 

2. 1번을 해결했다고 생각했음에도 불구하고 시간초과가 떠서 왜 그런지 고민해 보았다. 이유로는 visited밖에 날 수 없을거 같았다. 처음에는 visited를 popleft시키면서 visited를 처리해 주었는데, 그렇게 했을 때가 생길 수 있다. 

  예를 들어, [[1, 0], [0, 1]]이란 입력이 주어졌을 때, (0, 0)과 (1, 1)이 큐에 들어가고 (0, 0)은 visit 처리가 되지만 다음 상태인 (0, 1)과 (0, 1)이 처리되지 않기 때문에 2번 q에 들어가게 되고 그렇게 되면 불필요한 연산이 늘어나게 된다는 것을 알 수 있었다.

  --> 해당 코드를 제출한 결과는 통과가 되었다.

 

전체 코드는 아래와 같다.

 

고찰: 시간 관련하여 생각하는 습관을 더 기르도록 해야할 것같다. 자그마한 차이가 큰 결과의 차이를 가지고 오는 것을 알 수 있었다.