[BOJ]1697号:鬼ごっこ

1.質問

1697号：鬼ごっこ

秀彬N(0≦N≦100000)から弟K(0≦K≦100000)へ

移動

現在位置がXの場合、

、1秒後にX-1またはX+1に移動

は瞬時に移動し、1秒後に2*X、

に移動する
一番早い時間はです

2.アルゴリズム

BFS

X-1、X+1,2*Xを子とするツリー配置

ナビゲーションツリー

3.ソースコード

# BFS 탐색을 위한 queue 자료구조
from collections import deque

n, k = map(int, input().split())
MAX = 100000
time = [0] * (MAX + 1) # 수빈이 0에서 100000까지의 각 거리까지의 이동 시간 기록

def bfs(start):
    q = deque()
    q.append(start)
    
    while q:
        x = q.popleft()
        if x == k:
            return
        
        for nx in (x - 1, x + 1, x * 2):
            # 범위 내이고, 아직 이동시간이 기록되지 않았을 경우
            if 0 <= nx <= MAX and time[nx] == 0:
                q.append(nx)
                time[nx] = time[x] + 1
                
bfs(n)
print(time[k]) # k 위치에 기록된 이동시간 출력

4.失敗コード

from collections import deque

n, k = map(int, input().split())
MAX = 100000

def bfs(start, time):
    q = deque()
    q.append((start, time))

    while q:
        x, t = q.popleft()
        if x == k:
            return t
        
        for nx in (x - 1, x + 1, x * 2):
            if 0 <= nx <= MAX:
                q.append((nx, t + 1))

print(bfs(n, 0))

これは失敗コードです.現在の位置と時間がキューに格納されているため、メモリオーバーフローが発生しました.time listからtime[x]=0として保存されている場合、上記のコードはアクセスした場所をキューに再プッシュするため、不要なデータが格納され、メモリがオーバーフローする可能性があります.