글 읽기 - 1890 번 메모리초과 ㅠㅠ 도와주세요 복받으실거에요

tjdals333 3년 전 0

예외처리도 하고 무한루프 도는것도 방지하고 대충 예를 만들어서 풀었을때도

다 정답 나오는데 제출돌리면 메모리초과 나오네요 ㅠㅠ

from collections import deque

N=int(input())
arr=[]

for i in range(N):
    arr.append(list(map(int,input().split())))

dp=[[0]*N for i in range(N)]

def dpf(x,y): # bfs 스타일로 해결
    queue=deque()
    queue.append((x,y))

    while queue:
        xidx,yidx=queue.popleft()
        value=arr[xidx][yidx]
        if value==0: # 배열의 값이 0 일경우 queue에 추가하지말고 skip !
            continue
        xidx1=xidx # 오른쪽으로 이동 
        yidx1=yidx+value
        xidx2=xidx+value # 왼쪽으로 이동
        yidx2=yidx
        if 0<=xidx1<N and 0<=yidx1<N:
            dp[xidx1][yidx1]+=1 # dp 배열값 증가
            if xidx1==N-1 and yidx1==N-1: # 도착했을경우 skip !
                continue
            queue.append((xidx1,yidx1)) # 큐에 추가
        if 0<=xidx2<N and 0<=yidx2<N:
            dp[xidx2][yidx2]+=1 # dp 배열값 증가
            if xidx2==N-1 and yidx2==N-1: # 도착했을경우 skip !
                continue
            queue.append((xidx2,yidx2)) # 큐에 추가

dpf(0,0)
print(dp[N-1][N-1])

BFS를 할 때에는 반드시 방문 체크를 해야 합니다. 방문 체크를 하지 않으면 중복된 원소가 큐에 들어가게 되고, 그것들이 또다시 중복된 원소를 큐에 집어넣는 것이 반복되면서 지수적으로 큐에 들어가는 원소가 많아지게 됩니다. 예제 정도의 작은 입력으로는 순식간에 처리되겠지만, 문제의 최대 입력으로 최악의 경우를 만들면 우주가 멸망할 때까지 프로그램이 끝나지 않을 정도로 많은 원소를 큐에 넣게 될 것입니다.

tjdals333 3년 전 0

지식을 나눠주셔서 감사합니다 !!!!

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

문제

문제

출처

ICPC

1890 번 메모리초과 ㅠㅠ 도와주세요 복받으실거에요

tjdals333 3년 전 0

djm03178 3년 전 3

tjdals333 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말