글 읽기 - 파이썬 시간초과 ㅜㅜ 도와주세요

sehwa98 1년 전 0

BFS queue에 초기 익은 토마토를 모두 넣어주고, day 정보와 함께 함수를 구동하는 방식으로 진행했습니다.

어디에서 시간이 소모되었을까요? ㅜㅜ 고수님들 도와주세요 ㅜㅜ

import sys
from collections import deque

input = sys.stdin.readline
directions = [(1,0),(-1,0),(0,1),(0,-1)]
M,N = map(int,input().split())


def BFS(box):
    queue = deque()
    visitied = deque()
    day = 0 # 날짜 
    riped = 0 # 익은 토마토 개수 

    for x in range(N) :
        for y in range(M) :
            if box[x][y] == 1 : # 초기 1을 모두 queue에 넣음
                queue.append((x,y,day))
    while queue :
        nx,ny,day = queue.popleft()
        for d in directions :
            x, y = d[0] + nx, d[1] + ny
            if (0 <= x < N) and (0 <= y < M) : # 상하좌우 모든 방향 iter
                if not box[x][y] and (x,y) not in visitied : # 방문하려는 노드가 익지 않은 토마토이고, 방문한적이 없으면
                    box[x][y] = 1
                    queue.append((x,y,day+1))
                    visitied.append((x,y))
                    riped += 1 # 익은 토마토 개수
    return riped, day


box = []
raw = 0
for _ in range(N):
    box.append(list(map(int, input().split())))
    raw += box[_].count(0) # 익지 않은 토마토 개수 total

if not raw : # 익지 않은 토마토가 없으면 print 0
    print(0)
else : # 익지 않은 토마토가 있으면
    riped, day = BFS(box)
    if not (raw - riped) : # (초기 익지 않은 토마토 수) - (시간이 지나 익은 토마토 수) 가 0 이면 == 모든 익지 않은 토마토가 익었으면
        print(day)
    else : # 익지 않은 토마토가 존재하면
        print(-1)
    

djm03178 1년 전 0

deque에 대해 in을 수행하는 것은 그 덱에 있는 원소를 전체를 하나씩 보면서 일치하는 것이 있는지 찾는 것입니다. 즉, deque의 크기에 비례하는 시간이 걸립니다.

그냥 list를 이용해서 단 한 번에 확인해야 합니다.

sehwa98 1년 전 0

@djm03178 님이 말씀주신대로 visited를 제거하고 box를 통해 방문 여부를 확인하는 방법으로 바꾸니 바로 통과되네요! 감사합니다~

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

문제

문제

출처

ICPC

파이썬 시간초과 ㅜㅜ 도와주세요

sehwa98 1년 전 0

djm03178 1년 전 0

sehwa98 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말