백준 7576번 토마토 파이썬 (python code)

난이도: 실버1
번호: 7576번

 

 

 

처음에는 매번 모든 행과열의 데이터를 확인해서 1이면 확장하는 방식으로 만들었는데

시간초과가 발생했다.

 

초기작성코드(시간초과)

from sys import stdin
from copy import deepcopy



def tomato():
    day = 0
    prev= [0]
    while( any(0 in tomatobox[i] for i in range(M)) and prev != tomatobox):
        prev = deepcopy(tomatobox)
        q=[]
        for m in range(M):
            for n in range(N):
                if tomatobox[m][n]== 1:
                    if m < M - 1 and tomatobox[m + 1][n] == 0:
                        q.append([m+1,n])
                    if m > 0 and tomatobox[m - 1][n] == 0:
                        q.append([m-1,n])
                    if n < N - 1 and tomatobox[m][n + 1] == 0:
                        q.append([m,n+1])
                    if n > 0 and tomatobox[m][n - 1] == 0:
                        q.append([m,n-1])
        while q:
            tomatobox[q[-1][0]][q[-1][1]]=1
            q.pop()
        day+=1
    if ( prev != tomatobox):
        print(day)
    else:
        print(-1)

if __name__ == '__main__':
    N,M = map(int,stdin.readline().split())
    tomatobox=[]
    for i in range(M):
        tomatobox.append(list(map(int,stdin.readline().split())))
    tomato()

 

다른분들의 코드를 참고하였는데 초기에 1이들어있는 인덱스와 내가 확장시킨 인덱스만 확인하면 되는거였다.

지금보면 당연한데 생각을 못했다.

 

day를 계산하는 방법을 새로 만들었다.

확실히 더 bfs 스러워졌고 파이썬스러워진듯하다.

 

from sys import stdin
from collections import deque



def tomato():
    q= deque()
    day=-1
    for i in range(M):
        for j in range(N):
            if tomatobox[i][j] == 1:
                q.append([i, j])
    while q:
        for _ in range(len(q)):
            a, b = q.popleft()
            for i in range(4):
                x = a + dx[i]
                y = b + dy[i]
                if 0 <= x < M and 0 <= y < N and tomatobox[x][y] == 0:
                    tomatobox[x][y] = 1
                    q.append([x, y])
        day+=1

    if any(0 in tomatobox[i] for i in range(M)):
        print(-1)
    else:
        print(day)

if __name__ == '__main__':
    N,M = map(int,stdin.readline().split())
    tomatobox=[]
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]
    for i in range(M):
        tomatobox.append(list(map(int,stdin.readline().split())))
    tomato()