check 배열을 이차원으로 만들어서 첫 열에는 시간, 두번째 열에는 방법을 저장한다.
만약 방문한 적이 없다면 시간은 + 1, 방법은 지금 갯수 그대로
만약 방문한 적이 있고(다른 방법) 최단거리(원래 있던 거리랑 같아야함)로 왔다 -> 방법 + 1
ex. 1 4 와 같은 반례 처리가 매우 중요
1 -> 2- > 4 인데 X2 -> X2 일 수도 있고 +1 -> X2 일 수도 있다.
from collections import deque
n, k = map(int, input().split())
check = [[-1] * 2 for _ in range(100001)]
q = deque()
q.append(n)
check[n][0] = 0
check[n][1] = 1
while q:
x = q.popleft()
for y in [x -1, x + 1, 2 * x]:
if 0 <= y <= 100000:
if check[y][0] == -1:
q.append(y)
check[y][0] = check[x][0] + 1
check[y][1] = check[x][1]
elif check[y][0] == check[x][0] + 1:
check[y][1] += check[x][1]
print(check[k][0])
print(check[k][1])내가 푼 배열 행 3개짜리도 반례처리 해보기
^^~