글 읽기 - 시간초과/ 메모리초과 질문있습니다.

freestory2 1년 전 0

python3는 시간초과, pypy3는 메모리초과가 뜨네요

bfs이므로 vis 배열을 [이동한 횟수, 점프한 횟수]로 만들었고 점프횟수가 낮은 거로 갱신하면서 이동시켰습니다.

결과값을 가지는 res는 배열 말고 변수로 사용하여 시간, 메모리를 좀더 절약했고

마지막에 한칸짜리 케이스 예외처리도 해주었습니다.

그런데 한 50%쯤 진행되더니 시간초과/ 메모리초과가 뜨네요

어느 부분이 비효율적인지 제 눈으로는 못찾겠습니다. 도와주세요

from collections import deque

k = int(input())
w, h = map(int, input().split())
world = [list(map(int, input().split())) for _ in range(h)]

que = deque()
mv = [[0,1],[1,0],[0,-1],[-1,0],[-2,1],[-2,-1],[-1,2],[-1,-2],[1,2],[1,-2],[2,1],[2,-1]]
vis = [[[-1, 0] for _ in range(w)] for _ in range(h)]

vis[0][0] = [0, 0]
que.append([0,0])
res = 99999999999

def bfs():
  global res
  while len(que):
    now = que.popleft()
    nx, ny = now[0], now[1]
    nc, nt = vis[nx][ny][0], vis[nx][ny][1]
    for i in range(12):
      x, y = nx+mv[i][0], ny+mv[i][1]
      if x < 0 or x >= h or y < 0 or y >= w:
        continue
      if nt >= k and i >= 4:
        continue
      if world[x][y] == 0 and (vis[x][y][0] == -1 or vis[x][y][1]> nt):
        if i>= 4:
          vis[x][y] = [nc+1, nt+1]
        else:
          vis[x][y] = [nc+1, nt]
        if x == h-1 and y == w-1:
          if vis[x][y][0] < res:
            res = vis[x][y][0]
        que.append([x,y])

bfs()
if res == 99999999999:
  if w == 1 and h == 1:
    print(0)
  else:
    print(-1)
else:
  print(res)

rhasya 1년 전 1

로직상의 오류로 인해 que에 계속해서 데이터가 쌓이는 것으로 보입니다.

30
200 200
0 으로 채운 TC로 테스트를 해보세요

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

문제

문제

출처

ICPC

시간초과/ 메모리초과 질문있습니다.

freestory2 1년 전 0

rhasya 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말