[白俊7576]トマト

#7576
BFSを利用すれば良いと思います.
アクセス配列を用いて迷路問題を解決する場合と同様に,カウンタを1つ増やせばよいと考えられるが,迷路問題との違いは,異なる場所から同時に開始できることである.
この部分は、スタート地点(1人トマト)を全て行列に入れる方式が最初から解決しています.

初回試行-タイムアウト

まずアクセスすると当然少なくなるので、アクセスしていないものだけアップロードカウントする方式をとっています.でもタイムアウト...!

x,y=map(int,input().split())
matrix=[[0]*x for _ in range(y)]
visit=[[0]*x for _ in range(y)]
direct = [[0,1],[1,0],[-1,0],[0,-1]]
queue =[]

#matrix 만들기
for i in range(y) :
  new=input().split()
  for j in range(x) :
    matrix[i][j] = visit[i][j] = int(new[j])
    if matrix[i][j] == 1 :
      queue.append([i,j])

if len(queue) != 0 : #1인 토마토가 하나도 없으면 BFS 순회 할 필요 없음.
  while queue :
    i = queue[0][0]
    j = queue[0][1]
    queue.pop(0)
    for d in direct :
      di = i + d[0]
      dj = j + d[1]
      if (0<=di<y and 0<=dj<x) and matrix[di][dj]==0:
        visit[di][dj] = visit[i][j] + 1
        matrix[di][dj] = 1 #다시 탐색하지 않기 위해 1로 바꿔줌.
        queue.append([di,dj])

maximum=0
flag=0
for i in range(y) :
  for j in range(x) :
    if visit[i][j] == 0 : 
#bfs를 돌고도 방문하지 않은 부분 = 갈 수 없는 부분 = 모든 토마토를 익힐 수는 없다.
      flag = 1
      break
    elif visit[i][j] > maximum :
      maximum = visit[i][j]
  if flag == 1 : break

if flag == 1 : print(-1)
else : print(maximum-1)

2回目の試み-正しい

間違った理由が分かった.
BFSはキューを使用する方式であるため,Pythonのリストをappendとして挿入しpop(1)で削除し,pop(1)の時間的複雑度はO(N)に達する.
したがって、前にpop演算が必要な場合は、from collections import dequeを選択してライブラリを使用することが望ましい.
dequeはlistと似ていますが、時間の複雑さは大幅に減少します!

from collections import deque

x,y=map(int,input().split())
matrix=[[0]*x for _ in range(y)]
visit=[[0]*x for _ in range(y)]
direct = [[0,1],[1,0],[-1,0],[0,-1]]
queue = deque()

#matrix 만들기
for i in range(y) :
  new=input().split()
  for j in range(x) :
    matrix[i][j] = visit[i][j] = int(new[j])
    if matrix[i][j] == 1 :
      queue.append([i,j])

cnt=0

#bfs 탐험
if len(queue) != 0 :
  while queue :
    i = queue[0][0]
    j = queue[0][1]
    queue.popleft()
    for d in direct :
      di = i + d[0]
      dj = j + d[1]
      if (0<=di<y and 0<=dj<x) and matrix[di][dj]==0:
        visit[di][dj] = visit[i][j] + 1
        matrix[di][dj] = 1 #다시 탐색하지 않기 위해 1로 바꿔줌.
        queue.append([di,dj])
        cnt = visit[di][dj] #제일 마지막에 넣는 카운트를 출력하기 위한 변수

#토마토가 있지만 방문 할 수 없는 곳이 있는지, 다 방문했다면 얼마나 걸리는지 출력하는 부분
flag=0
for i in range(y) :
  for j in range(x) :
    if visit[i][j] == 0 : #bfs를 돌고도 방문하지 않은 부분 = 갈 수 없는 부분 = 모든 토마토를 익힐 수는 없다.
      flag = 1
      break
  if flag == 1 : break

if flag == 1 : print(-1)
elif cnt == 0 : print(cnt)
else : print(cnt-1)