[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를 자식으로 하는 트리 구성
• 해당 트리를 BFS 탐색

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이 아닌 곳에는 다시 방문하지 않는데 위 코드는 방문했던 곳도 다시 큐에 push 하므로 불필요한 데이터들이 저장되어 메모리 초과가 발생한 것 같다.