글 읽기 - pypy3 시간초과

blackrose18 2년 전 0

4프로에서 자꾸 시간초과가 뜨네요.....

import sys

m, n = map(int, sys.stdin.readline().split())

tree = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
queue = []
day = -2

for i in range(m):
    for j in range(n):
        if tree[j][i] == 1:
            queue.append([j, i])

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

while queue:
    y, x = queue[0]
    del queue[0]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < m and 0 <= ny < n and tree[ny][nx] == 0:
            queue.append([ny, nx])
            tree[ny][nx] = tree[y][x] + 1

flag = False

for i in tree:
    for j in i:
        if j == 0:
            flag = True
            break
        else:
            day = max(day, j)
    if flag:
        print(-1)
        break

if not flag:
    print(day - 1)

tjdwns5063 2년 전 0

파이썬에서 큐는 보통 deque로 구현합니다

지금 이렇게 배열로 구현하면 한번 큐에서 (x. y)가 나올때 큐 전체를 순회해야해서 시간이 오래걸립니다

deque를 사용해서 구현하면 맞을듯 합니다!

blackrose18 2년 전 0

queue의 popleft() 함수보다 그냥 배열의 제일 앞 값을 없애주는 게 더 빠를줄 알았는데...... 뭔가 배신감이 드네요 ㅎㅎㅎ 감사합니다!

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

문제

문제

출처

ICPC

pypy3 시간초과

blackrose18 2년 전 0

tjdwns5063 2년 전 0

blackrose18 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말