[백준7576] 토마토

문제

---

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

7576번: 토마토

 

생각의 흐름

---

일반적인 BFS 문제이다. 처음에 행렬을 하나씩 돌면서 1인 곳의 위치 (x,y)를 q에 넣어주고, 여기서 하나씩 빼서 해당 위치에 대해 BFS로 탐색을 시도한다. q에서 뺄 때마다 cnt의 값을 1씩 더해주고 이를 나중에 q의 원소갯수와 비교하는 방식으로 day를 갱신하여 소요날짜를 계산한다. (이 부분은 말로 설명하니 좀 모호한데 코드를 보면 좀 더 명확히 이해가 될 것이다.)

처음에 행렬의 원소를 하나씩 검사하면서 이미 다 익어있는 상태인지 검사하고, 위의 과정을 거치고 나서는 아직까지 0이 남아있는지를 검사하여 익을 수 없는 토마토가 있는지를 판별한다 . 

 

깨달은 점

---

처음에 queue를 이용하여 구현을 하였더니 답은 맞았는데 시간초과가 났었다.(pypy로 시도했을 때조차도....) 원인을 찾던 중 python의 queue 모듈은 멀티쓰레드를 처리하기 위한 동기화 과정을 거치기 때문에 collections.deque보다 느리다는 것을 알게 되었다. 이 부분을 고려하여 deque로 구현을 하였더니 시간 초과 문제가 해결되었다.

자세히 알지는 못하지만 찾아보니 deque의 간단한 삽입/삭제의 시간복잡도가 O(1)로 빠르다는 것을 알 수 있었다.

파이썬에는 정말 많은 실용적인 라이브러리들이 있지만 비슷한 것 같더라도 각기 다른 성능을 보인다는 것을 유념해야 겠다!!!!

 

코드

---

#import queue
from collections import deque
import sys

M,N = map(int, sys.stdin.readline().split())
tomato = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
all_one = [[1]*M for _ in range(N)]

# 이미 다 익어있는 상태인지 검사
zero = 0
for i in range(N):
    for j in range(M):
        if tomato[i][j]==0:
            zero += 1
if zero == 0:
    print(0)
else:
    #q = queue.Queue()
    q = deque()
    dx, dy = [-1,1,0,0], [0,0,-1,1]

    for i in range(N):
        for j in range(M):
            if tomato[i][j]==1:
                q.append((i,j))

    day = 0
    size = len(q)
    cnt = 0
    while len(q):
        if size==cnt:
            day += 1
            size=len(q)
            cnt = 0
        x, y = q.popleft()
        cnt += 1
        for i in range(4):
            new_x = x + dx[i]
            new_y = y + dy[i]
            if 0<=new_x<N and 0<=new_y<M:
                if tomato[new_x][new_y] == 0:
                    tomato[new_x][new_y] = 1
                    q.append((new_x, new_y))


    # 익을 수 없는 토마토가 존재하는지 검사
    still_zero = 0
    for i in range(N):
        for j in range(M):
            if tomato[i][j]==0:
                still_zero += 1
    if still_zero == 0:
        print(day)
    else:
        print(-1)