백준 13913번 숨바꼭질 4

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

13913번: 숨바꼭질 4

BFS로 n이 k가 되는 최단거리와 최단경로를 찾는 문제이다.

n > k 인경우는 항상 worst case가 되는데 그래서 해당 케이스를 위한 로직을 따로 만들었다.

일단은 정답이라고 채점이 되었는데 이게 맞는지 모르겠다.

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

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

if n > k:
    print(n-k)
    for i in range(n,k-1,-1):
        print(i,end=' ')
else:
    visited = [0]*100001

    q = deque()

    q.append((n,[n]))

    Shortest_path = []
    while q:
        a, SP = q.popleft()

        if a == k:
            Shortest_path = SP
            break

        visited[a] = 1

        for each in [2,1,-1]:
            tmp = a
            if each == 2:
                if 0 <= tmp*each <= 100000:
                    if not visited[tmp*each]:
                        q.append((tmp*each,SP + [tmp*each]))

            else:
                if 0 <= tmp + each <= 100000:
                    if not visited[tmp + each]:
                        q.append((tmp + each,SP +[tmp + each]))

    print(len(Shortest_path) - 1)
    print(*Shortest_path)