[백준] 13913. 숨바꼭질4 (Python)

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

13913번: 숨바꼭질 4

 

💫 가장 빨리 동생을 찾는 시간과 그 루트를 출력해주어야 한다.

💫 check 배열의 앞으로 들어갈 값의 위치에 현재 위치를 적어주었고, 역추적해주었다.

 

from collections import deque

def BFS(start, target):
    q = deque()
    q.append((start, 0)) # start, cnt
    Mincnt = 0
    Minpath = []
    check = [-1]*100001
    while q:
        now, cnt = q.popleft()
        if now == target:
            Mincnt = cnt
            break

        path = [now-1, now+1, now*2]

        for p in path:
            if 0<= p <= 100000 and check[p] == -1:
                check[p] = now # check[앞으로 갈 위치]에 현재 위치 넣어주기
                q.append((p, cnt+1))

    now = target
    for _ in range(Mincnt+1): # 루트 역으로 추척
        Minpath.append(now)
        now = check[now]

    return Mincnt, Minpath[::-1]

n, k = map(int, input().split())

res = BFS(n, k)

print(res[0])
print(*res[1])