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

tmvhswlqkq 4년 전 0

메모리초과는 처음 겪었는데 어떻게 해야할지 모르겠네요ㅠㅠ

힌트나 도움좀 주세요 python쓸 때 메모리를 특히 많이 잡아먹는 부분이 있을까요ㅠㅠ

#5213
from collections import deque

N = int(input())
a=[]
q=deque()
able = [-N,-1,N-1,-N+1,1,N]
back =[]
c = [False]*(N*N-N//2)
res = 10000


def bfs():
    while q:
        x,y,i,cnt = q.popleft()
        c[i] = True
        back.append((i,cnt))
        #print(i,cnt)
        #global N
        if i == (N*N-(N//2))-1:
            global res
            lst_res =[]
            if res > cnt:
                res = cnt
                 

        for k,j in enumerate(able):
            if 0<= i+j and i+j < (N*N)-(N//2):
                if k<=2: # [1]
                    if a[i][0]==a[i+j][1] and c[i+j]==False:
                        q.append((a[i+j][0],a[i+j][1],i+j,cnt+1))
                
                else:  # [0]
                    if a[i][1]==a[i+j][0] and c[i+j]==False:
                        q.append((a[i+j][0],a[i+j][1],i+j,cnt+1))


if __name__ == '__main__':

    for i in range(N*N-N//2):
        x,y = map(int,input().split())
        a.append((x,y))

        
    q.append((a[0][0],a[0][1],0,1))
    bfs()
    qs = deque()
    res_lst=[]

    for i in range(len(back)-1,-1,-1):
        if back[i][1]== res:
            qs.append([back[i][0] , i])
            while qs:
                num, l= qs.popleft()
                res_lst.append(num+1)
                for j in range(l-1,-1,-1):
                    find = False
                    for k in able:
                        if back[l][0]+k == back[j][0] and back[l][1] == back[j][1]+1:
                            qs.append((back[j][0],j))
                            find = True
                            break
                    if find == True:
                        break
            if len(res_lst) == res:
                break

    print(res)
    for i in range(len(res_lst)-1,-1,-1):
        print(res_lst[i],end=' ')
    print()
        

                            



    

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

문제

문제

출처

ICPC

5213번 메모리초과 질문입니다ㅠ

tmvhswlqkq 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말