백준 13913 숨바꼭질 4 - 파이썬

문제.

풀이.

이 문제도 경로를 저장하는 배열을 저장해서 연산마다 경로를 추가했는데

이 방법으로하면 메모리가 초과된다.

이 방법은 이동한 경로를 나타내는 배열을 하나 선언한뒤

어디로 이동했는지 표시하고 목표지에 도착했을때, 해당 위치에서부터 어떻게 이동했는지를 체크하면된다.

 

소스코드.

import sys
from collections import deque

def path(x):
    arr = []
    temp = x
    for i in range(matrix[x] + 1):
        arr.append(temp)
        temp = move[temp]
    arr.reverse()
    print(*arr)

def BFS(n):
    queue = deque()
    queue.append(n)

    while queue:
        x = queue.popleft()
        for i in range(3):
            if dx[i] == 2:
                nx = x *2
            else:
                nx = x + dx[i]

            if (0 <= nx < idx):
                if matrix[nx] == 0:
                    matrix[nx] = matrix[x] + 1
                    move[nx] = x
                    if nx == k:
                        print(matrix[k])
                        path(nx)
                        return
                    queue.append(nx)

dx = [1, -1, 2]

input = sys.stdin.readline
n, k = map(int, input().split())
idx = 200000
matrix = [0] * idx
move = [0] * idx

if n == k:
    print(0)
    print(n)
else:
    BFS(n)