7576번 - 토마토(python3)

문제 링크 : https://www.acmicpc.net/problem/7576

7576번: 토마토

이전 단지번호붙이기 문제와는 다르게 BFS로 풀어야 하는 문제입니다. M*N 박스의 각 칸에 토마토가 보관되는데 1은 익은 토마토, 0은 익지 않은 토마토, -1은 빈 공간입니다. 하루가 지날 때마다 익은 토마토 주위의 익지 않은 토마토들이 익게 되고, 최소 며칠이 지나야 모든 토마토가 다 익을 수 있는지 구하면 됩니다. 초기에 다 익어있으면 0을, 모든 토마토가 익지 못하는 경우에는 -1을 출력하면 됩니다.

 

BFS다보니 queue를 사용하게 되는데, 그냥 list, list.pop(0)을 사용하게 되면 시간 초과가 생겨 collections에서 deque를 가져와 사용합니다. list.pop(0)은 deque.popleft()로 대신합니다. 그냥 list에서 list.pop(0)을 쓰면 시간복잡도가 O(N)인데 deque.popleft()의 경우는 O(1)이라고 합니다.(참고 링크 : https://stackoverflow.com/questions/32543608/deque-popleft-and-list-pop0-is-there-performance-difference)

from collections import deque

m, n = map(int, input().split())
tom = []
queue = deque()
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
tmp = m*n #초기 0 개수(익어야 하는 토마토 수)
day = -1
rip = 0 #익은 토마토 수

def bfs():
    global rip
    x, y = queue.popleft()
    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 and tom[new_x][new_y] == 0:
            tom[new_x][new_y] = 1 #안 익은 주위의 토마토 1로 변경
            rip += 1 #익은 개수 update
            queue.append([new_x, new_y])


for _ in range(n):
    tom.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        if tom[i][j] == 1: #초기에 익은 토마토를 queue에 추가
            queue.append([i,j])
            tmp -= 1
        elif tom[i][j] == -1: #빈 공간 체크
            tmp -= 1


if tmp == 0: #초기에 모두 다 익어있다
    print(0)
else:
    while queue:
        num = len(queue)
        for _ in range(num):
            bfs()
        day += 1

    if tmp == rip: #모두 익는게 가능하다
        print(day)
    else: #모두 익는게 불가능하다
        print(-1)

초기 상태에서 0, 1의 개수(tmp, rip)를 파악하고, 가능한 모든 토마토가 익은 뒤 전체 익은 토마토의 개수(rip)와 초기 0의 개수(tmp)를 비교해서 같으면 익는데 걸린 날짜를, 다르면 -1을 출력합니다. 초기에 tmp = 0이면 모든 토마토가 익은 상태이기 때문에 0을 출력합니다. 그나저나 모두 비어있을 경우에도 0을 출력하도록 했는데 맞네요.

 

매일 익기 전 len(queue)를 뽑아서 해당 횟수만큼 bfs를 돌립니다. 그렇지 않으면 어디까지가 1일동안 토마토가 익는 것인지 확인이 불가능합니다. 저 tmp, rip 변수와 len(queue)체크를 없앨 수 있다면 코드가 더 짧아질 수 있을 것 같네요.