글 읽기 - 똑같은 코드인데 한 쪽은 메모리 초과가 납니다...

jec0101 1년 전 0

구조는 비슷한데 한쪽은 메모리 초과가 납니다 흑흑

채점 시작하기도 전에 뜨던데 뭐가 문제일까요??

##### 통과한 코드 #####
from collections import deque, defaultdict
N, K = map(int, input().split())
MAX = 100000

def bfs(start, visited):
    if start == K:
        return 0
    q = deque()
    q.append((N, 0))
    visited[N] = True
    
    while q:
        idx, time = q.popleft()
        if idx == K:
            return time
        for pos in [idx*2, idx+1, idx-1]:
            if 0 <= pos <= MAX and not visited[pos]:
                visited[pos] = True
                if pos == idx*2:
                    q.appendleft((pos, time))
                else:
                    q.append((pos, time+1))

def solution(N, K):
    visited = [False] * (MAX+1)
    print(bfs(N, visited))

solution(N, K)

        
        
##### 메모리 초과 #####
from collections import deque
N, K = map(int, input().split())
MAX = 100000

def bfs(start, visited):
    if start == K:
        return 0
    q = deque()
    q.append((N, 0))
    visited[N] = True
    
    while q:
        idx, time = q.popleft()
        positions = [idx-1, idx+1]
        if idx*2 == K:
            return time
        if idx*2 >= 0 and idx*2 <= 100000 and not visited[idx*2]:
            visited[idx*2] = True
            q.appendleft((idx*2, time))
        for pos in positions:
            if pos >= 0 and pos <= 100000 and not visited[pos]:
                if pos == K:
                    return time+1
                q.append((pos, time+1))

def solution(N, K):
    visited = [False] * (MAX+1)
    print(bfs(N, visited))

solution(N, K)

djm03178 1년 전 1

후자는 57번째 줄에서 큐에 넣기 전에 visited에 체크하지 않고 있습니다.

dbtjd1928 1년 전 1

윗분 말씀을 정정해드리자면,

메모리 초과 코드 line 57에서는 visited[pos] = True로 바꿔주는 작업이 빠져있습니다.

jec0101 1년 전 0

아.... 맞네요 ㅋㅋㅋㅋㅋㅋ 감사합니다!!

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

문제

문제

출처

ICPC

똑같은 코드인데 한 쪽은 메모리 초과가 납니다...

jec0101 1년 전 0

djm03178 1년 전 1

dbtjd1928 1년 전 1

jec0101 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말