이번 문제는 BFS를 통해 해결하였다. 처음에는 큐에 방문한 위치를 저장하는 리스트를 함께 넣어, 다음 이동할 위치가 방문한 위치 리스트에 들어있지 않을 경우에만 이동하도록 작성하였다. 그러나 이 과정에서 시간 초과가 발생하였고, visited리스트를 사용하기로 하였다. visited리스트에는 각 점까지의 최단 거리를 저장하도록 하였고, k에 도착하면 answer를 1 증가시켰다. 결과적으로는 visited[k]값이 최단거리가 되고, answer가 가짓수가 된다.

Code

from collections import deque
n, k=map(int, input().split())
dw, dt=[1, -1, 0], [1, 1, 2]
visited=[-1 for _ in range(100001)]
answer = 0
def bfs(x):
    global answer
    q=deque()
    q.append(x)
    visited[x]=0
    while q:
        cur=q.popleft()
        if cur==k:
            answer+=1
            continue
        for i in range(3):
            nxt=(cur+dw[i])*dt[i]
            if 0<=nxt<100001:
                if visited[nxt]==-1 or visited[nxt]>=visited[cur]+1:
                    visited[nxt]=visited[cur]+1
                    q.append(nxt)
bfs(n)
print(visited[k])
print(answer)