글 읽기 - 파이썬 BFS 시간초과가 나네요

postcookie 2년 전 0

안녕하세요. 토마토(7576) 문제를 풀다가 시간초과가 나서 질문드립니다.

deque를 썼고, 조금 돌다가 시간초과가 나는 상황인데요.

원인이 뭔지 모르겠습니다.

의심되는 건 max_day를 while 루프 안에서 계산해주는 것 때문 아닌가 싶은데

잘못 짚고 있다는 생각도 들어서 어딜 고쳐야할지 모르겠네요.

각종 테스트케이스는 전부 맞습니다.

from collections import deque
import sys
input = sys.stdin.readline

def bfs(box, tomatoes, n, m):
  dx = [1, -1, 0, 0]
  dy = [0, 0, -1, 1]
  qu = deque(tomatoes)
  max_day = 0

  while qu:
    x, y, day = qu.popleft()

    for i in range(4):
      nx = dx[i] + x
      ny = dy[i] + y
      if nx < 0 or nx >= n or ny < 0 or ny >= m:
        continue
      if box[nx][ny] == 0:
        box[x][y] = 1
        qu.append([nx, ny, day + 1])
    
    max_day = max(max_day, day)
  
  for i in range(n):
    for j in range(m):
      if box[i][j] == 0: return -1
  return max_day


m, n = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(n)]
tomatoes = []

for i in range(n):
  for j in range(m):
    if box[i][j] == 1:
      tomatoes.append([i, j, 0])

print(bfs(box, tomatoes, n, m))

postcookie 2년 전 0

자문자답입니다. 역시 max 연산이 문제였나 봅니다.

max 연산 빼고 아예 box[nx][ny]를 box[x][y] + 1으로 바꾸니 잘됩니다.

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

문제

문제

출처

ICPC

파이썬 BFS 시간초과가 나네요

postcookie 2년 전 0

postcookie 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말