글 읽기 - 파이썬 시간초과

blytheej 5년 전 0

시간초과가 뜨는데 어디서 시간을 잡아먹는지 모르겠네요 ㅠㅠ

bfs사용해서 풀고 있습니다!

비슷한 문제인 미로문제는 같은 방식으로 해결되었습니다 ㅠㅠ

import sys
from sys import stdin
sys.setrecursionlimit(100000)

m, n = [int(x) for x in stdin.readline().split()]  #가로 세로
box = []
search = []
#토마토 받기
for i in range(n):
    box.append([int(x) for x in stdin.readline().split()])


def bfs():
    while len(search) > 0:
        for i in range(len(search)):
            x, y = search.pop(0)
            if x > 0 and box[x - 1][y] == 0:
                search.append((x - 1, y))
                box[x - 1][y] = box[x][y] + 1
            if x + 1 < n and box[x + 1][y] == 0:
                search.append((x + 1, y))
                box[x + 1][y] = box[x][y] + 1
            if y > 0 and box[x][y - 1] == 0:
                search.append((x, y - 1))
                box[x][y - 1] = box[x][y] + 1
            if y + 1 < m and box[x][y + 1] == 0:
                search.append((x, y + 1))
                box[x][y + 1] = box[x][y] + 1


alll = 0  # 1: 안익음 0 : 다 익음
iszero = 0
for each in box:
    if 0 in each:
        iszero = 1
        break
if iszero == 0:
    print(0)
else:
    #처음 토마토 찾기 및 방문 확인
    for i in range(n):
        for j in range(m):
            if box[i][j] == 1:
                search.append((i, j))
    if len(search) > 0:
        day = bfs()
    for each in box:
        if 0 in each:
            alll = 1
            break
    if alll == 1:
        print(-1)
    else:
        print(max(max(box))-1)

dragons6641 5년 전 2

저도 지금까지 같은 문제를 겪고 있는데요

파이썬에서 pop(0) 을 하게되면 0번째 인덱스의 값을 리턴할 뿐만 아니라

1번째 인덱스의 값을 0번째로, 2번째 인덱스의 값을 1번째로, ... , n번째 인덱스의 값을 n - 1번째로 옮기는 작업을 하기 때문에

많은 시간을 잡아 먹는다고 합니다! (O(n))

그래서 저는 아래와 같은 식으로 양방향 queue 모듈을 import해서 사용했습니다.

하지만 수정한 코드는 뜬금없이 런타임 에러가 나서

아직 성공하지 못했네요...

import collections;

queue = collections.deque([]);

temp = queue.popleft(); // pop 대신 popleft 사용

queue.append([i, j, 0]); // append는 그대로 사용 가능

blytheej 5년 전 0

이제 막 파이썬을 시작해서 pop이 그렇게 오래걸리는지 몰랐네요ㅠㅠ

queue 이용해서 해봐야겠어요 감사합니다!!

성공하셨길..

rucy007 5년 전 0

저도 같은 문제로 헤매고 있었는데

queue 모듈로 변경하니 해결됐습니다 ㅠㅠㅠ

정말 감사합니다

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

문제

문제

출처

ICPC

파이썬 시간초과

blytheej 5년 전 0

dragons6641 5년 전 2

blytheej 5년 전 0

rucy007 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말