글 읽기 - 평범한 BFS인거같은데 메모리 초과가 나네요

hsw0194 3년 전 0

q에 넣은 후에 체크를 해서 메모리초과가 나는거같아서

q에 넣기전에 체크하고 끝내려고 했는데 그래도 메모리 초과가 나네요.

어느부분에서 조절할수 있을까요?

from sys import stdin
from collections import deque

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

# n은 세로의 길이
# m은 가로의 길이
n, m = map(int, stdin.readline().split())
grid = [[0] * (n + 1) for _ in range(m + 1)]
start_y = start_x = 0
visit = set()

for i in range(n):
  s = stdin.readline().rstrip("\n")
  for j in range(len(s)):
    grid[i + 1][j + 1] = int(s[j])
    if int(s[j]) == 2:
      start_y = i + 1
      start_x = j + 1


def ans():
  bfs()


def bfs():
  q = deque()
  q.append((start_y, start_x, 0))
  visit.add((start_y, start_x))

  while q:
    y, x, dist = q.popleft()

    # if grid[y][x] != 0 and grid[y][x]!=2:
    #   print("TAK")
    #   print(dist)
    #   return

    for k in range(4):
      ny = y + dy[k]
      nx = x + dx[k]

      if ny > n or nx > m or ny < 1 or nx < 1:
        continue

      if not (ny, nx) in visit and grid[ny][nx] != 1:
        if grid[ny][nx] != 0 and grid[ny][nx] != 2:
          print("TAK")
          print(dist+1)
          return
        else:
          visit.add((ny, nx))
          q.append((ny, nx, dist + 1))

  print("NIE")


ans()

hsw0194 3년 전 0

set을 그냥 배열로 만들어서

메모리초과는 해결했는데

100프로에서 런타임에러가 나오네요.. 당황스럽습니다

도와주세요 ㅠㅠ

from sys import stdin
from collections import deque

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

# n은 세로의 길이
# m은 가로의 길이
n, m = map(int, stdin.readline().split())
grid = [[0] * (n + 1) for _ in range(m + 1)]
start_y = start_x = 0
# visit = set()
visit = [[False] * 3001 for _ in range(3001)]

for i in range(n):
  s = stdin.readline().rstrip("\n")
  for j in range(len(s)):
    grid[i + 1][j + 1] = int(s[j])
    if int(s[j]) == 2:
      start_y = i + 1
      start_x = j + 1


def ans():
  bfs()


def bfs():
  q = deque()
  q.append((start_y, start_x, 0))
  # visit.add((start_y, start_x))
  visit[start_y][start_x]=True

  while q:
    y, x, dist = q.popleft()

    # if grid[y][x] != 0 and grid[y][x]!=2:
    #   print("TAK")
    #   print(dist)
    #   return

    for k in range(4):
      ny = y + dy[k]
      nx = x + dx[k]

      if ny > n or nx > m or ny < 1 or nx < 1:
        continue

      if not visit[ny][nx] and grid[ny][nx] != 1:
        if grid[ny][nx] != 0 and grid[ny][nx] != 2:
          print("TAK")
          print(dist + 1)
          return
        else:
          # visit.add((ny, nx))
          visit[ny][nx]=True
          q.append((ny, nx, dist + 1))

  print("NIE")


ans()

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

문제

문제

출처

ICPC

평범한 BFS인거같은데 메모리 초과가 나네요

hsw0194 3년 전 0

hsw0194 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말