글 읽기 - 메모리 초과 질문입니다

chm4332 1년 전 0

BFS로 푸는 문제처럼 보여 너비 우선 탐색을 했고, 메모리 초과가 날 것 같아 visited 처리도 했으며, 여러 반례들 모두 통과가 되는데요

메모리 초과(50%) 를 어떻게 개선해야 할 지 모르겠습니다 ㅠㅠ

from collections import deque
t = int(input())

def bfs(x):
  queue = deque()
  c = 0
  cnt = 0
  queue.append((x, c, cnt))
  visited[x] = 1
  while queue:
    cnt = 1
    i, j, cnt = queue.popleft()
    if i < 0 or i > y :
      continue
    visited[i] = 1
    
    if i == y and j==1:
      return cnt
    if (i+j+1) > 0 and (i+j+1) <= y: #and visited[i+j+1] == 0:
      visited[i+j+1] = 1
      queue.append((i+j+1, j+1, cnt+1))
    if (i+j) > 0 and (i+j) <= y:  #and #visited[i+j] == 0:
      visited[i+j] = 1
      queue.append((i+j, j, cnt+1))
    if (i+j-1) > 0 and (i+j-1) <= y:  #and #visited[i+j-1] == 0:
      visited[i+j-1] = 1
      queue.append((i+j-1, j-1, cnt+1))

      
while t != 0:
  x, y = map(int, input().split())
  visited = [0] * (y+1)
  print(bfs(x))
  t -= 1

djm03178 1년 전 0

visited라는 배열을 쓰시긴 했는데, 실제로는 값을 대입할 뿐 방문이 되었는지 여부를 전혀 확인하지 않고 있어서 큐에 중복된 원소들이 들어갑니다.

왜 and ~ 부분을 주석 처리하셨나요?

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

문제

문제

출처

ICPC

메모리 초과 질문입니다

chm4332 1년 전 0

djm03178 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말