글 읽기 - 7576 토마토 파이썬 시간초과 문제,,,

qqaz54 4년 전 0

계속 해봐도 시간초과가 나오네요,,,

우선 토마토의 갯수를 세서 -1이거나 0인 경우를 판단했습니다

그런 다음 1인 칸들을 모두 큐에 삽입해서 그 큐를 BFS 했습니다.

그다음 만들어진 배열에서 최대값을 출력하는 간단한 과정인데 시간초과가 계속 나오네요,,,

질문글 참조하여 큐를 deque로 바꿔보았지만 여전히 시간초과입니다.

제 코드에서 어디 비효율적인 부분이 있는걸까요..

고수 여러분들의 많은 태클 부탁드립니다...

from collections import deque
import sys

input = sys.stdin.readline

M, N = map(int, input().split())
farm = [list(map(int, input().split())) for _ in range(N)]
visit = [[False for _ in range(M)] for __ in range(N)]
q = deque()

def bfs():

    while q.__len__():
        next_node = q.popleft()
        X = next_node[0]
        Y = next_node[1]
        C = next_node[2]
        visit[Y][X] = True
        farm[Y][X] = C
        
        if X > 0 and farm[Y][X - 1] == 0 and not visit[Y][X - 1]:
            q.append([X - 1, Y, C + 1])
            visit[Y][X - 1] = True
            farm[Y][X - 1] = C + 1
        
        if X < M - 1 and farm[Y][X + 1] == 0 and not visit[Y][X + 1]:
            q.append([X + 1, Y, C + 1])
            visit[Y][X + 1] = True
            farm[Y][X + 1] = C + 1
            
        if Y > 0 and farm[Y - 1][X] == 0 and not visit[Y - 1][X]:
            q.append([X, Y - 1, C + 1])
            visit[Y - 1][X] = True
            farm[Y - 1][X] = C + 1
            
        if Y < N - 1 and farm[Y + 1][X] == 0 and not visit[Y + 1][X]:
            q.append([X, Y + 1, C + 1])
            visit[Y + 1][X] = True 
            farm[Y + 1][X] = C + 1

def solve():
    cnt = 0

    for i in range(N):
        for j in range(M):
            if farm[i][j] == 1:
                q.append([j, i, 1])
                cnt += 1
                
    if cnt == 0: return -1
    if cnt == M * N: return 0

    
    bfs()

    sol = -2
    tmp = 1
    
    for i in range(N):
        for j in range(M):
            sol = farm[i][j] if farm[i][j] > sol else sol
            tmp *= farm[i][j]

    if tmp == 0: return -1
    else: return sol - 1
        

print(solve())

qqaz54 4년 전 2

해결했습니다. deque를 잘못써서 느렸네요.

queue는 pop이 O(N)인데 deque는 O(1)입니다.

파이썬으로 푸시는 분들은 참고하세요

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

문제

문제

출처

ICPC

7576 토마토 파이썬 시간초과 문제,,,

qqaz54 4년 전 0

qqaz54 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말