글 읽기 - 시간초과(파이썬)

wbjkwjj 3년 전 0

시간초과가 발생할 가능성이 높은 구문을 알려주시면 감사하겠습니다.

리스트도 큐로 바꾸어보았지만 계속 시간초과가 뜨네요

from sys import stdin
from queue import Queue
from collections import deque
m,n=map(int,stdin.readline().split())
tom=[]
q=Queue()
howlong=0
for i in range(n):
    row=list(map(int,stdin.readline().split()))
    tom.append(row)

allcan=True

def cango(y,x):
    return y>=0 and y<=n-1 and x>=0 and x<=m-1
def adj(y,x):
    return [(y-1,x),(y+1,x),(y,x-1),(y,x+1)]

for j in range(n):
    for i in range(m):
        if tom[j][i]==1:
            q.put((j,i))

while(not q.empty()):
    pos=q.get()
    ypos,xpos=pos[0],pos[1]
    for k in adj(ypos,xpos):
        ny,nx=k[0],k[1]
        if cango(ny,nx):
            if tom[ny][nx]==0:
                q.put(k)
                tom[ny][nx]=tom[ypos][xpos]+1
                if tom[ny][nx]>howlong:
                    howlong=tom[ny][nx]
for i in tom:
    for j in i:
        if j==0:
            allcan=False
            break
print(howlong-1 if allcan else -1)

snapflip20 3년 전 1

queue.Queue 대신에 collections.deque를 사용해보세요.

queue는 멀티스레드 환경을 지원하는 모듈이기 때문에 deque보다 훨씬 느립니다.

wbjkwjj 3년 전 0

감사합니다. 주신 조언 덕분에 해결했습니다.

좋은 하루 보내세요^^

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과(파이썬)

wbjkwjj 3년 전 0

snapflip20 3년 전 1

wbjkwjj 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말