글 읽기 - 7576 토마토문제 파이썬 시간초과 오류가납니다

mirusu400 4년 전 0

질문 검색글에 있는 대부분의 테크닉을 적용해 시간을 줄여도 3% 이상 퍼센티지가 올라가지 않고 바로 시간초과 오류가 나네요..

익지 않은 토마토 확인
값 입력을 받을때 0으로 입력받은 값의 좌표를 따로 배열에 저장해서 이들만 검사하는 방식으로 속도를 줄였습니다

2. 불가능한 경우 확인

이전에 시도한 케이스와 익은 토마토의 갯수가 똑같은 경우 불가능한 경우로 처리했습니다

3. 토마토 익게 만들기

익은 토마토 좌표를 큐에 저장해 이에 해당하는 상하좌우 좌표에 해당하는 리스트의 값을 익게 만들어주고 그 좌표를 다시 큐에 저장했습니다

빠른 입출력까지 적용했는데 왜 느린걸까요..?

import collections
import sys
Matrix = []
BefMatrix = collections.deque()
tomato_pos_list = collections.deque()
untomato_pos_list = collections.deque()
day=0
unripetomato=0
xy = list(map(int, sys.stdin.readline().split(' '))) #x y로 받아옴

for i in range(xy[1]):
    Matrix.append(list(map(int, sys.stdin.readline().split(' '))))
    for j in range(0,xy[0]):
        if(Matrix[i][j] == 1):
            tomato_pos_list.append([i,j])
        if(Matrix[i][j] == 0):
            untomato_pos_list.append([i,j])
while True:
    beftomato=unripetomato
    unripetomato=0
    
    #Check if all riped
    for k in range(0,len(untomato_pos_list)): #익지 않은 토마토 갯수 중 아직도 익지 않은 것을 확인
        aa = untomato_pos_list.popleft() #익었을경우 -> pop, 안익었을경우 -> 다시 큐에
        y = aa[0]
        x = aa[1]
        if(Matrix[y][x] == 0):
            unripetomato+=1
            untomato_pos_list.append([y,x])

    #안익은 토마토가 없을시 break
    if(unripetomato == 0):
        break

     #Check if impossible
    if(beftomato == unripetomato): #안익은 토마토 갯수가 이전 시행과 동일할시 불가능
        day = -1
        break
    
    day+=1

    # 익은 토마토의 상하좌우를 익게 만듬
    for i in range(0,len(tomato_pos_list)):
        aa = tomato_pos_list.popleft()
        y = aa[0]
        x = aa[1]
        if(x != 0 and Matrix[y][x-1] == 0):
            Matrix[y][x-1] = 1
            tomato_pos_list.append([y,x-1])
            
        if(x != xy[0]-1 and Matrix[y][x+1] == 0):
            Matrix[y][x+1] = 1
            tomato_pos_list.append([y,x+1])
            
        if(y != 0 and Matrix[y-1][x] == 0):
            Matrix[y-1][x] = 1
            tomato_pos_list.append([y-1,x])
            
        if(y != xy[1]-1 and Matrix[y+1][x] == 0):
            Matrix[y+1][x] = 1
            tomato_pos_list.append([y+1,x])

   

print(day)

mirusu400 4년 전 0

1번 케이스와 2번 케이스 관련 소스코드 부분을 수정해 해결했습니다.

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

문제

문제

출처

ICPC

7576 토마토문제 파이썬 시간초과 오류가납니다

mirusu400 4년 전 0

mirusu400 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말