글 읽기 - 메모리 초과 이유를 알고싶습니다

leehojin0719 3년 전 0

안녕하세요.

계속 메모리 초과가 뜨는데 이유를 알고 싶습니다.

다른분들은 visited리스트를 따로 만들어서 말처럼 이동할 수 있는 횟수를 체크하시던데

저는 큐에 x좌표 y좌표 이동 횟수, 말처럼 이동할 수 잇는 횟수를 4개 다 넣었습니다. 이게 메모리 초과의 이유일까요?

주석 보시고 이해 안되시는 내용은 댓글 달아주세요. 답글남길께요.

감사합니다.

from collections import deque
import sys
input=sys.stdin.readline
cnt=int(input())
m,n=map(int,input().split())
graph=[]
for i in range(n):
    graph.append(list(map(int,input().split())))
hx=[2,2,-2,-2,1,1,-1,-1]
#말의 이동횟수
hy=[1,-1,1,-1,2,-2,2,-2]
#말의 이동횟수
dx=[1,-1,0,0]
#일반 이동횟수
dy=[0,0,1,-1]
#일반 이동횟수

def check(x,y):
    if 0<=x<n and 0<=y<m and graph[x][y]==0:
        #범위 내에 있고 값이 0이라면 return True
        return True
    return False

def bfs():
    q=deque()
    q.append((0,0,0,0))
    #x,y,이동 횟수, 말처럼 이동할 수 있는 횟수
    while q:
        x,y,count,flag=q.popleft()
        #x,y,이동 횟수, 말처럼 이동할 수 있는 횟수
        if x==n-1 and y==m-1:
            #값에 도달하면 이동 횟수 출력
            return count
        for i in range(4):
            #일반적인 이동
            nx=x+dx[i]
            ny=y+dy[i]
            if check(nx,ny):#체크함수
                q.append((nx,ny,count+1,flag))
                #x,y,이동 횟수+1, 말처럼 이동할 수 있는 횟수 그대로
        if flag<cnt:
            #말처럼 이동할 수 있다면
            for i in range(8):
                nx=x+hx[i]
                ny=y+hy[i]
                if check(nx,ny):#체크함수
                    q.append((nx,ny,count+1,flag+1))
                    #x,y,이동 횟수+1, 말처럼 이동할 수 있는 횟수+1
    return -1
print(bfs())

nahwasa 3년 전 0

현재 visited 없이 진행하고 계셔서 그렇습니다.

이 경우 말그대로 기하급수적으로 bfs가 확장됩니다.

상하좌우 4방향만 봐도 처음 0,0에서 0,1과 1,0으로 간애에서 다시 0,0으로 오고 다시 0,1과 1,0으로 가고...

모든 칸에서 해당 로직이 반복되므로 애초에 메모리 초과 안나셨어도 시간초과 나셨을꺼에요.

leehojin0719 3년 전 1

아 그렇군요 감사합니다 ㅎㅎ

visited를 써서 다시 풀어봐야겠네요

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

문제

문제

출처

ICPC

메모리 초과 이유를 알고싶습니다 - 파이썬

leehojin0719 3년 전 0

nahwasa 3년 전 0

leehojin0719 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말