[백준] 7576-토마토

문제바로가기

import sys
sys.setrecursionlimit(10**6)

m, n = map(int, input().split())
graph = [[] for _ in range(n)]
day = 0

for i in range(n):
    tmp = list(map(int, input().split()))
    graph[i]=tmp
data = []*(n*m)
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            data.append([i,j])

while(data):
    i = [0, 0, 1, -1]
    j = [1, -1, 0, 0]
    for _ in range(len(data)):
        idx = data.pop(0)
        for k in range(4):
            ni = i[k]+idx[0]
            nj = j[k]+idx[1]
            if (0<=ni<n) and (0<=nj<m) and (graph[ni][nj]==0):
                graph[ni][nj]=1
                data.append([ni, nj])
    day += 1

for row in graph:
    if 0 in row:
        print(-1)
        break
else:
    print(day-1)

초기에 쓴 코드는 메모리 초과가 떴다. 원인은 크게 두 가지.
첫 번째는 data를 리스트로 선언한 것이고,
두 번째는 i, j 리스트를 while문이 돌 때마다 생성하는 것이다.

최대한 라이브러리 안쓰고 직접 구현하고 싶어서 data를 일부러 deque를 사용하지 않았는데.. 리스트로 구현할 땐 시간복잡도 O(n), deque로 구현할 때는 O(1)이라니까 그렇게 수정해주자.

from collections import deque
import sys
sys.setrecursionlimit(10**6)

m, n = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

queue = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            queue.append((i, j))

day = 0

while queue:
    for _ in range(len(queue)):
        x, y = queue.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
                graph[nx][ny] = 1
                queue.append((nx, ny))
    day += 1
    
for row in graph:
    if 0 in row:
        print(-1)
        break
else:
    print(day-1)