백준 13913 숨바꼭질4

haruponea·2021년 3월 25일
0

BOJ

목록 보기
25/41

문제 링크https://www.acmicpc.net/problem/13913

풀이
bfs의 경로를 저장하는 문제입니다. vis리스트에 이전 칸의 위치를 저장하고 큐에는 걸린 시간도 함께 전달해 줍니다.

Python

from collections import deque
>
n, k = map(int, input().split())
vis = [-1] * 100001
q = deque()
q.append((n, 0))
while q:
    cur, count = q.popleft()
    if cur == k:
        print(count)
        break
    for next in [cur * 2, cur + 1, cur - 1]:
        if 0 <= next <= 100000 and vis[next] == -1:
            q.append((next, count + 1))
            vis[next] = cur
path = []
for _ in range(count + 1):
    path.append(cur)
    cur = vis[cur]
print(*path[::-1])

0개의 댓글