[BOJ]7576 토마토

www.acmicpc.net/problem/7576

7576번: 토마토

 

시작점이 여러개인 BFS 문제이다.

첫 시작점만 리스트로 넣어주면 되는 문제.

 

하지만

시간초과가 계속 났다.

이유는 queue를 이용하지 않아서.

평소에 나는 list.pop(0)을 사용하는데, 이번엔 이걸 쓰면 시간초과가 나는 문제였다.

이걸 deque.popleft()로 바꿧더니 풀리는 문제..

from collections import deque
import sys
def solution(sp : list ,tomato : list,v : list):
    N,M=len(tomato),len(tomato[0])
    q=sp
    X=[0,0,1,-1]
    Y=[1,-1,0,0]
    while q:
        c_x,c_y=q.popleft()
        for i in range(4):
            n_x=c_x+X[i]
            n_y=c_y+Y[i]
            if n_x>=0 and n_x<N and n_y>=0 and n_y<M:
                if tomato[n_x][n_y]==0:
                    if v[n_x][n_y]>v[c_x][c_y]+1:
                        q.append((n_x,n_y))
                        tomato[n_x][n_y]=1
                        v[n_x][n_y]=v[c_x][c_y]+1

    return -1 if sum(list(map(lambda x : x.count(0),(*tomato))))!=0 else max(map(max,v))

N,M=(map(int,input().split(' ')))
tomato=[]
sp=[]
v=[[10000]*N for i in range(M)]
for i in range(M):
    r=list(map(int,input().split(' ')))
    tomato.append(r)
    for idx,j in enumerate(r):
        if j==1:
            sp.append((i,idx))
            v[i][idx]=0
        elif j==-1:
            v[i][idx]=0
print(solution(sp,tomato,v))