백준 7576 [토마토] 파이썬

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

7576번: 토마토

맨 처음에는 두가지 큐를 이용해서, 현재 진행하는 큐와 값을 받을 큐로 나누어서 문제를 해결하려고 하였다.

---> 시간초과 발생

# 백준 7576 시간초과
from collections import deque
import sys
input = sys.stdin.readline
global answer
answer = 0
dr=[0,0,-1,1]
dc=[1,-1,0,0]
M, N = map(int, input().split())
box = []
tomatos = deque([])
news = deque([])
for i in range(N):
    box.append(list(map(int, input().split())))
    for j in range(M):
        if box[i][j] == 1:
            news.append([i, j])


def bfs():
    global answer
    while news:
        while news:
            row_, col_ = news.popleft()
            tomatos.append([row_, col_])
        while tomatos:
            row, col = tomatos.popleft()
            box[row][col] = 1
            for i in range(4):
                r, c = row+dr[i], col+dc[i]
                if 0 <= r < N and 0 <= c < M:
                    if box[r][c] == 0:
                        news.append([r, c])
        answer += 1


bfs()
check = 0
for line in box:
    if check == 1:
        break
    if 0 in line:
        check = 1
        break
if check == 1:
    print(-1)
else:
    print(answer-1)

 

 

 

 

 

# 백준 7576
from collections import deque
import sys
input = sys.stdin.readline
answer = 0
dr = [0, 0, -1, 1]
dc = [1, -1, 0, 0]
M, N = map(int, input().split())
box = []
tomatos = deque([])
for i in range(N):
    box.append(list(map(int, input().split())))
    for j in range(M):
        if box[i][j] == 1:
            tomatos.append([i, j])


def bfs():
    while tomatos:
        row, col = tomatos.popleft()
        for i in range(4):
            r, c = row+dr[i], col+dc[i]
            if 0 <= r < N and 0 <= c < M:
                if box[r][c] == 0:
                    box[r][c] = box[row][col]+1
                    tomatos.append([r, c])


bfs()
check = 0
for i in range(N):
    for j in range(M):
        if box[i][j] == 0:
            check = 1
        answer = max(answer, box[i][j])
if check == 1:
    print(-1)
else:
    print(answer-1)

시간초과를 해결하지 못하고 고민하다 다른 분의 풀이에서 아이디어를 얻었다.

두 개의 큐를 만들 필요 없이, 값을 1씩 증가시켜주면 되는 것이었다....

 

열심히하자...ㅠㅠ