글 읽기 - Python 메모리초과 질문드립니다.

kk0640 4년 전 0

많이 차지하는 변수로는 location, temp,visited 입니다.

location은 매 초마다 초기화하면서 갈 수 있는 위치 다 넣어놓고 k값 나오면 나오도록 했습니다.

temp는 location 에서 갈 수 있는 위치를 모두 담는데 그중에 visitied에 없는것만 넣도록하고

visited는 말그대로 왔던 곳을 저장하는 변수입니다.

어디서 메모리 초과가 나오는 걸까요?

n,k = map(int,input().split())
cnt =0

def bfs(n,k,cnt):
    con =1
    visited = set()
    location = set()
    location.add(n)
    while(con):
        if(k in location):
            con =0
            return cnt
        else:
            cnt+=1
            temp=list()
            while(location):
                temp_loc =location.pop()
                temp.append(temp_loc)
                visited.add(temp_loc)
            for i in range(len(temp)):
                if(temp[i]+1 not in visited):
                    location.add(temp[i]+1)
                if(temp[i]-1 not in visited):
                    location.add(temp[i]-1)
                if(temp[i]*2 not in visited):
                    location.add(temp[i]*2)

cnt = bfs(n,k,cnt)
print(cnt)

kk0640 4년 전 0

해결했습니다. 방에 위치에는 제한이 있는데 제가 그 제한을 넣지않아서 메모리초과가 났습니다. 제한을넣으니 해결되었습니다.

n,k = map(int,input().split())
cnt =0

def bfs(n,k,cnt):
    con =1
    visited = set()
    location = set()
    location.add(n)
    while(con):
        if(k in location):
            con =0
            return cnt
        else:
            cnt+=1
            temp=list()
            while(location):
                temp_loc =location.pop()
                temp.append(temp_loc)
                visited.add(temp_loc)
            for i in range(len(temp)):
                if(temp[i]+1 not in visited):
                    if(temp[i]+1<=100000):
                        location.add(temp[i]+1)
                if(temp[i]-1 not in visited):
                    if(temp[i]-1>=0):
                        location.add(temp[i]-1)
                if(temp[i]*2 not in visited):
                    if(temp[i]*2<=100000):
                        location.add(temp[i]*2)

cnt = bfs(n,k,cnt)
print(cnt)

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

문제

문제

출처

ICPC

Python 메모리초과 질문드립니다.

kk0640 4년 전 0

kk0640 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말