글 읽기 - 시간초과 질문드립니다.

kgood1 4년 전 0

토마토 문제를 bfs를 사용하여 풀어보았습니다

시간초과로 통과를 못하고있는대 어느 부분이 비효율적인지 지적해주시면 감사하겠습니다

그리고 마지막 check리스트에서(3중리스트?) 가장 큰 값을 찾아내는 더 좋은 방법이 있는지 궁금합니다

저는 리스트를 모두 합쳐서 최댓값을 구했습니다

import sys
from collections import deque
def input():
    return sys.stdin.readline()
dx=[0,0,1,-1,0,0]
dy=[0,0,0,0,1,-1]
dz=[1,-1,0,0,0,0]
M,N,H=map(int,input().split())
check=[[[-1]*M for i in range(N)]for j in range(H)] #날짜를 위해
arr=[[list(map(int, input().split())) for _ in range(N)] for _ in range(H)]
queue=deque()
for i in range(H):
    for j in range(N):
        for m in range(M):
            if arr[i][j][m]==0:
                continue
            else:
                check[i][j][m] = 0 #arr에서 -1이나 1일때는 이미 방문한곳으로
                if arr[i][j][m]==1:
                    queue.append([i,j,m])
#bfs
while queue:
    p,q,r=queue.popleft()
    for i in range(6):
        np=p+dz[i]
        nq=q+dy[i]
        nr=r+dx[i]
        if np<0 or np>=H or nq<0 or nq>=N or nr<0 or nr>=M:
            continue
        elif  check[np][nq][nr]==-1:
            check[np][nq][nr]=check[p][q][r]+1
            queue.append([np,nq,nr])
Max=max(sum(sum(check,[]),[])) #check 배열들을 합쳐서 최댓값을 구함
Min=min(sum(sum(check,[]),[])) #미치지 못한 곳 -1이 있으면 -1 출력
if Min==-1:
    print(-1)
else:
    print(Max)

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

문제

문제

출처

ICPC

시간초과 질문드립니다.

kgood1 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말