[백준/파이썬] 13913번

📍백준 13913번 문제

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

코드

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

start, end = map(int, input().split())

visited = [-1] * 100001
road = [-1] * 100001
que = deque()

visited[start] = 0
que.append(start)

while que:
    cur = que.popleft()
    if cur == end:
        break
    for i in [cur + 1, cur - 1, 2 * cur]:
        if 0 <= i < 100001 and visited[i] == -1:
            visited[i] = visited[cur]+1
            road[i] = cur
            que.append(i)
res = []
temp = cur
for i in range(visited[end] + 1):
    res.append(temp)
    temp = road[temp]
print(visited[end])
print(' '.join(map(str, res[::-1])))

풀이

다음 위치 값을 인덱스로 설정하고, 현재 위치를 배열의 값에 넣어준다
visited[next] = cur으로 저장해야, 마지막에 경로를 출력할 수 있다.