[백준/13913/Gold IV] 숨바꼭질4 - BFS, 최단경로를 visited로 메모리초과 안나게 관리하기 with Python

문제

• bfs에서 메모리초과 안나게 visited로 이전 경로 추적하는 방식

https://www.acmicpc.net/problem/13913

 

WHY? 알고리즘 선택 이유

• BFS
  • 최단 경로, 최단 시간으로 N에서 K에 가는 방법을 구해야하니까

 

풀이1 - 메모리 초과

import sys
from collections import deque
input = sys.stdin.readline

'''
n -> x -> k
1초 x-1, x+1 / 2 * x
가장 빠르게 찾을 수 있는 시간 -> 최단 경로 찾기 BFS

3개의 선택지 중, 항상 k와 가장 가까운 위치로 이동하기
'''
n, k = map(int, input().split())
queue = deque([(n, 0, [n])]) #bfs 큐에 (x, 누적 시간, 누적 경로) 저장

while queue:
    x, t, path = queue.popleft()

    if x == k:
        print(t) #최단 시간
        print(*path, sep=" ") #최단 경로
        break

    queue.append((x-1, t+1, path + [x-1]))
    queue.append((x+1, t+1, path + [x+1]))

    if x * 2 < 200000:
        queue.append((x*2, t+1, path + [x*2]))

풀이2 - 메모리 초과 해결

from collections import deque

'''
가장 빠르게 찾을 수 있는 시간 -> 최단 경로 찾기 BFS
'''
n, k = map(int, input().split())
queue = deque([(n, 0)]) #bfs 큐에 (x, 누적 시간) 저장

**visited = [-1] * 100001 # visited[현재위치] = 바로 이전의 위치**
visited[n] = n

while queue:
    x, t = queue.popleft()

    if x == k:
        print(t) #최단 시간
        break

    for next in (x - 1, x + 1, x * 2):
        # 범위 내의 숫자이고, 아직 방문한 적없는 위치일 경우에만 큐에 넣기
        # 방문한 곳을 또 방문하면 최단경로가 되지 않음!
        **if 0 <= next <= 100000 and visited[next] == -1:**
            queue.append((next, t + 1))
            visited[next] = x

# 최단 경로 - k번째부터 visited에 저장된 바로 이전의 위치를 출력
idx = k
path = [k]

while idx != n:
    path.append(visited[idx]) # 이전 위치 경로에 넣기
    idx = visited[idx]

print(*path[::-1])