글 읽기 - 파이썬으로 풀어봤는데 자꾸 시간초과가 뜨네요

hyunbo 4년 전 0

여기서 어떻게 시간을 줄일 수 있을까요?

import sys, queue
input = sys.stdin.readline

M, N, H = map(int, input().split())

q = queue.Queue()
matrix = []
num_data = 0
token = False
for k in range(H):
    square = []
    for j in range(N):
        line = list(map(int, input().split()))
        square.append(line)
        for i in range(len(line)):
            if line[i] == 1:
                q.put((i, j, k))
                num_data += 1
            elif line[i] == 0:
                token = True
                num_data += 1

    matrix.append(square)

## 처음부터 모든게 다 익어 있는 경우의 수를 제거하는 게 중요 queue에 들어가면 시간을 많이 잡아먹는다.
if not token :
    print(0)
    sys.exit()

days = 0
total = 0
while not q.empty():
    total += q.qsize()
    for _ in range(q.qsize()):
        (i, j, k) = q.get()

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

        for idx in range(6):
            x, y, z = i + dx[idx], j + dy[idx], k + dz[idx]
            if (0<= x < M) and (0<= y < N) and (0<= z < H) \
                and (matrix[z][y][x] == 0):
                matrix[z][y][x] = 1
                q.put((x, y, z))
    days += 1

# print("total, num_data", total, num_data)
if total == num_data:
    print(days - 1)
else:
    print(-1)

djm03178 4년 전 0

queue.Queue는 멀티스레드를 위한 모듈이기 때문에 매우 느리다고 합니다.

collections.deque를 대신 사용하세요.

hyunbo 4년 전 0

그랬군요.! 상당히 시간을 썼는데 정답은 deque 였네요. 감사합니다.

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

문제

문제

출처

ICPC

파이썬으로 풀어봤는데 자꾸 시간초과가 뜨네요

hyunbo 4년 전 0

djm03178 4년 전 0

hyunbo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말