글 읽기 - 메모리 초과가 나오는데... 어떻게 해결해야 할까요?

zidane92 3년 전 0

전체적인 구성은 2차원 리스트에서 시작이 뚜(1)이라면, 뚜루루뚜루(12212)가 되는 경로를 모든 칸에서 부터 다 찾아보는 형식입니다.

메모리 초과가 출력이 되는데... 어떻게 해결할 수 있을까요?

R,C=map(int,input().split())
num=R*C//5+1
L=[1,2,2,1,2]*num
index=0
L2=[]
for i in range(R):
    L2.append(L[index:index+C])
    index+=C
del L
v=[]
target=[1,2,2,1,2]
cnt=0

def dfs(r,c,now, now2):
    global cnt
    v.append((r,c))
    if len(now)<5 and L2[r][c]==target[len(now)]:
        now.append([r,c])
        now2.append(L2[r][c])
        if now2==target:
            cnt+=1
        if r>0 and (r-1, c) not in v: #Up
            dfs(r-1,c,now,now2)
        if r+1<len(L2) and (r+1,c) not in v: #Down
            dfs(r+1,c, now,now2)
        if c>0 and (r, c-1) not in v: #Left
            dfs(r,c-1,now,now2)
        if c+1<len(L2[0]) and (r,c+1) not in v: #Right
            dfs(r,c+1,now,now2)
        del now[-1], now2[-1]
    del v[-1]

for i in range(R):
    for j in range(C):
        if L2[i][j]==1:
            dfs(i,j,[],[])
print(cnt)

djm03178 3년 전 0

R과 C가 최대 크기이면 1억 칸이 넘게 만들어지기 때문에 모든 칸을 저장하기 위한 메모리를 할당할 수가 없습니다.

또, 담을 수 있다고 해도 모든 칸에서부터 탐색해서 모든 경우의 수를 찾는 것은 시간 초과를 피할 수 없습니다.

모든 칸을 탐색하지 않고도 답을 찾는 방법을 생각해야 합니다. 참고로, 이 문제는 굉장히 어려운 편에 속하는 문제입니다.

zidane92 3년 전 0

@djm03178 답변감사합니다 그럼 하나 질문은... R과 C가 맥시멈일때, 2차원 리스트를 사용하지도 않고 이 문제를 처리할 수 있는 방법이 존재한다는 말씀이신건가요?????

djm03178 3년 전 0

네. 규칙을 잘 찾아서 일부분만 보고도 해결할 수 있습니다.

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

문제

문제

출처

ICPC

메모리 초과가 나오는데... 어떻게 해결해야 할까요?

zidane92 3년 전 0

djm03178 3년 전 0

zidane92 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말